Tuesday, August 2, 2011

Binary Tree Tutorial - Basics

Hello All!

Before I get into the details of Binary Tree, lets first understand what is actually a Tree.

So, What is a Tree?

As simple as that. Anything that has a root and has branches and has leaves is a Tree. Simple.
150
|
110
/   |   \
220    9   504
Lets see what does it mean in terms of a data structure.

The root node (or simply root) is the node at the top of the tree. In our case it is the one containing 150.

The parent of a node is the one directly connected to it from above. In our example, 150 is the parent of 110, 110 is the parent of 220, 150 has no parent, etc.

child is a node connected directly below the starting node. Thus 220,9,504 are child of 110, 110 is a child of 150, etc.

Nodes with the same parent are called siblings. So, 220,9,504 are siblings in our example.

The height of a node in a tree is the length of a longest path from the node to a leaf. The height of a tree is the height of its root.

The depth of a node is the length of the unique path from the root to the node.

Note: In a tree, any parent can have any number of child nodes. (Keep in mind that we are just talking about a tree, not binary tree).

Alright then, this was simple. Lets move forward now.

So, What is a Binary Tree?

A binary tree is similar to a tree, but not quite the same. For a binary tree, each node can have zero, one, or two children.

In addition, each child node is clearly identified as either the left child or the right child. Thus there is a definite left-right ordering of the child nodes. Even when a node has only one child, that child must be identified as either the left child or the right child.
-
/     \
*         3
/     \
4       5

Alright. Then what the hell is Binary search tree?

Its simple too. Let me explain.

Binary Search Tree

Well, we know that a binary search is fast because it divides the number of items that need to be searched in half at each step. The only downside is that binary search requires the list to be sorted. Let's try something crazy and actually store the items in the list just like they would be found if we did a binary search for each. That is, the start of the data structure would be the middle item. If we move to the left then we see the middle of the left subset. Basically we're taking a linear list and changing it to an explicit binary search structure:

[0][1][2][3][4][5][6][7][8][9]

becomes
5

/           \

2               8

/   \           /   \

1       4       7       9

/       /       /

0       3       6
A binary search tree is a binary tree in which the data in the nodes is ordered in a particular way. To be precise, starting at any given node, the data in any nodes of its left subtree (not only left node, but the complete left subtree) must all be less than the item in the given node, and the data in any nodes of its right subtree (not only right node, but the complete right subtree)  must be greater than or equal to the data in the given node. For strings, alphabetical ordering is often used. For records of data, a comparison based on a particular field (comparator/comprable) is often used.

How does one create a binary search tree?

One way is to first sort the items, then follow the methodology explained in above example. That will create a BALANCED Binary Search Tree.

Another way to do so is by starting with an empty binary search tree and adding the data items one by one. The first item becomes the root. The next item is placed in either a left child or right child node, depending on the ordering. The third item is compared to the root, we go left or right depending on the result of the comparison, etc. until we find the spot for it.

But assume that the data/array that you started with was already sorted. Then you will end up something like this.

1
\
2
\
3
\
4
...


It is still a BST, but all the nodes will have one right child till the end. Thus in this case, the benefits of BST for searching/inserting will not be so much useful here as anytime you need to search/insert - one needs to iterate over the elements in right child.

Hope this clarifies the fundamentals. Now lets go through different ways to traverse the Binary Search Tree.

Balanced Binary Tree

A balanced tree is a tree which is balanced - it has roughly the same height on each of its sub-nodes. a balanced binary search tree will have equal heights (plus or minus one) on the left and right sub-trees of each node.

If the tree is balanced on both sides, only then while searching anything - we can divide tree into halves during every operation. Otherwise, dividing tree into 2 halves for every lookup does not hold valid. This ensures that operations on the tree always are guaranteed to have O(lg n) time, rather than the O(n) time that they might have in an unbalanced tree. 




Next > : Binary Trees Traversal Algorithm - Inorder, Preorder, Postorder



3 comments:

  1. Along with just one single small you can sometimes win all as well as get rid of everything. Your speediest form of investment decision there is, no need to hang on months, many weeks, as well as many years for the earnings to start moving with. binary

    ReplyDelete
  2. I really appreciate information shared above. It’s of great help. If someone want to learn Online (Virtual) instructor lead live training in TECHNOLOGY , kindly Contact MaxMunus
    MaxMunus Offer World Class Virtual Instructor led training on TECHNOLOGY. We have industry expert trainer. We provide Training Material and Software Support. MaxMunus has successfully conducted 1,00,000 + trainings in India, USA, UK, Australlia, Switzerland, Qatar, Saudi Arabia, Bangladesh, Bahrain and UAE etc.
    For Demo Contact us.
    Saurabh srivastava
    MaxMunus
    E-mail: saurabh@maxmunus.com
    Skype id: saurabhmaxmunus
    Ph:+918553576305
    www.MaxMunus.com


    ReplyDelete