Binary Tree

-
A tree is a hierarchical data structure which consists of a set of nodes. A tree is a graph with no cycles. 

Binary Tree is a special type of tree, in which each node can only have a maximum of 2 children.

In Binary Tree each node consists of : 

 1. Data
2. Pointer to left node
3. Pointer to right node
TREE TERMINOLOGY : 

Root
- Node with no parent, only one in a tree

 Leaf
- Any node with no children

 Parent 
- If a node is directly above node x, then it is parent of node x

 Child 
- If a node is directly below node x, then it is child of node x

 Ancestor 
- If a node is in the path from root to node x, then is ancestor of node x

 Descendant 
- If a node y is ancestor of node x, then node x is descendant of node y

 Siblings
-Set of nodes that have the same parent node



A Binary Tree can be implemented in C++ as :
 #include <iostream>  
 using namespace std;  
 // Implementation of Binary Tree in C++  
 struct tree{  
      int data;  
      struct tree * left;  
      struct tree * right;  
 };  
 int main()  
 {            
      struct tree *root;  
      struct tree A;  
      struct tree B;  
      struct tree C;  
      root = &A;  
      root->left = &B;  
      root->right = &C;  
      root->data = 10;  
      B.data = 20;  
      C.data = 30;  
      cout<<A.data<<endl;     // 10  
      cout<<root->left->data<<endl; // 20  
      cout<<root->right->data<<endl; // 30  
 }

The binary tree implemented by the program above would look like : 

Height of tree :

If the tree contains no nodes, its height is 0.
Otherwise, it 1 + height of taller subtree. [1 is for root and take max(left,right)]

 The height of the tree above is 2. 

 Level of node :

 The level of node n is the number of nodes on the path from root to node n.

 For root, level is 1. For every other node it is 1 + level of its parent

 Some properties :

 1. Maximum number of nodes in a binary tree of height h is ((2^h)-1)
2. Maximum number of nodes at level I of a binary tree is (2^(I-1))
3. In binary tree, number of leaf nodes is always one more than nodes with two children.

Comments

Post a Comment

Popular posts from this blog

In Place Algorithms

-
I n-Place Algorithms are required to solve those problems which have limited memory constraints. You are not allowed to use extra memory and hence all operations need to be performed on the original data structures themselves. Usually, the algorithms should use O(1), constant memory. You are allowed to declare variables but not complete data structures. For example, you are given an array [1,2,2,4] and you need to delete all values which are equal to 2. One approach could be by checking each element of the array. If it is 2 then skip otherwise store the value in a new array and at the end of the loop[ when traversed every element of array ], return the new array. But this approach is not In-Place as it requires O(n) memory [ Worst case when no element of given value in array ]. For an In-Place algorithm we would need to delete the elements with value in the original array and then return the original array as the answer to the problem. 
Read more

References in C++

-
References in C++ are very important as they can help you significantly reduce the running time of your code. A reference is simply another name to the same data value. For example, here x_ref is a integer reference to x : int x = 10; int & x_ref = x; // reference initialization cout<<x_ref; // x_ref and x are same, i.e. 10 x_ref = 20; cout<<x; // x is now 20 A reference is declared by using the & sign [the & sign is also used to get memory location of a variable].  It is necessary to initialize a reference at the time it is declared. It is because you cannot have NULL references, so you need to initialize an explicit value to which declared reference is a reference to.  When you modify a reference, the original value also changes. Another example, string s = "Hello, this is original string"; string &x = s; x = "Modified string"; cout<<x; // outputs Modified string cout<<s; // outputs Modi...
Read more