#### 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** :

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.