The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Trees

A Tree is a hierarchical data structure which is represented using linked nodes. Every tree has a root node
( topmost node in the tree ) and a pointer to the root node is used to traverse the tree and perform other operations. Every node contains a value and pointers or links to its child nodes. This section of the tutorial focuses on algorithms based on Binary Trees and Binary Search Trees which are discussed below.

A Binary Tree is a data structure in which every node has atmost two child nodes ( left and right ) i.e every node has a value and 0 , 1 or 2 pointers. If a node does not have any child node, then it is known as leaf node. As mentioned above, the entire binary tree is accessed using a pointer to the root node.

A Binary Search Tree is a Binary Tree with additional constraints or properties which are mentioned below :
1 ) Left subtree of a node contain values which are less than the node's value.
2 ) Right subtree of a node contain values which are greater than the node's value.
3 ) Left and right subtrees are also binary search trees.
4 ) Duplicate values are not allowed.

Following figure visualizes a Binary Tree and a Binary Search Tree :

tree

In the above Binary Tree , 5 is the root node with 8 and 4 being the children of root node. In the Binary Search Tree , 11 is the root node and all the nodes including the root node satisfy the properties of binary search tree.

Tree Traversal
There are three different kind of traversals depending on the order in which nodes are visited.
PreOrder Traversal Parent node is visited first, then Left child and finally Right child.
Inorder Traversal Left child is visited first, then Parent and finally Right child.
PostOrder Traversal Left child is visited first, then Right child and finally the Parent.

For the Binary Tree shown above, the three traversals are :
PreOrder : 5 , 8 , 3 , 6 , 13 , 4 , 11 , 2
InOrder : 3 , 8 , 13 , 6 , 5 , 11 , 2 , 4
PostOrder : 3 , 13 , 6 , 8 , 2 , 11 , 4 , 5

For the Binary Search Tree shown above, the three traversals are :
PreOrder : 11 , 4 , 2 , 9 , 6 , 10 , 19 , 4
InOrder : 2 , 4 , 6 , 9 , 10 , 11 , 14 , 19
PostOrder : 2 , 6 , 10 , 9 , 4 , 14 , 19 , 11

Observe that inorder traversal of a Binary Search Tree visits the nodes in sorted order.
Now, keeping in mind these basic concepts of binary and binary search tree, let's solve some problems.

Back | Next

All problems on Trees
* Implement the inorder , preorder and postorder traversal mechanisms of a tree
* Implement an algorithm to insert a node in a Binary Search Tree ( BST )
* Implement an algorithm to find the height of a Binary Tree
* Implement an algorithm to get the level of a node in a Binary Tree assuming root node to be at level 1
* Get the root to leaf path in a Binary Tree such that the sum of the node values in that path is minimum among all possible root to leaf paths
* Print all the ancestors of a given node in a Binary Tree
* Replace all the node values with the sum of the node values of ancestral nodes in a Binary Tree
* Check if the given tree is a sum tree i.e value at each node is equal to the value of all elements in its left subtree and right subtree
* Given a Binary Tree, create another tree which is a mirror image of the given tree
* Construct a tree, given its inorder and preorder traversals
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Search Tree
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Tree
* Compute the Diameter of a given Binary Tree
* Check if a given tree is a Binary Search Tree ( BST )