Binary Tree - Types and Traversal

-
Some of the common types of Binary Tree are listed below :

 Full Binary Tree 
- In a full binary tree, each node has either 0 or 2 children.
- Each node is either leaf or has exactly 2 children.

Complete Binary Tree 
- All levels are full except possibly last.
- All nodes in the last level are aligned towards the left. 



Perfect Binary Tree 
- All nodes have 2 children except leaf.
- All leaf nodes are at the same level.


Balanced Binary Tree 
- Very good performance, O(log n) Insertion, Deletion and Search
- Every level above the lowest is full
- Diff is maximum 1 between left subtree and right subtree



Degenerate/Pathological Binary Tree 
- Each node has one child except leaf


Traversal


Preorder
Node is visited before its left and right subtrees

Postorder
Node is visited after both subtrees

Inorder
Visit left subtree, then visit node and finally right subtree





Binary Tree Traversals can be implemented by using recursive functions. 

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