/binary_trees

Primary LanguageC

Binary Trees

A Binary Tree is a hierarchical data structure in which each node has at most two children generally referred as left child and right child.

Each node contains three components:

  • Pointer to left subtree
  • Pointer to right subtree
  • Data element

The topmost node in the tree is called the root. An empty tree is represented by NULL pointer.

Binary Tree: Common Terminologies

  • Root: Topmost node in a tree.
  • Parent: Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent.
  • Child: A node directly connected to another node when moving away from the root.
  • Leaf/External node: Node with no children.
  • Internal node: Node with atleast one children.
  • Depth of a node: Number of edges from root to the node.
  • Height of a node: Number of edges from the node to the deepest leaf. Height of the tree is the height of the root.

In the above binary tree we see that root node is A. The tree has 10 nodes with 5 internal nodes, i.e, A,B,C,E,G and 5 external nodes, i.e, D,F,H,I,J. The height of the tree is 3. B is the parent of D and E while D and E are children of B.

Advantages of Trees

Trees are so useful and frequently used, because they have some very serious advantages:

  • Trees reflect structural relationships in the data.
  • Trees are used to represent hierarchies.
  • Trees provide an efficient insertion and searching.
  • Trees are very flexible data, allowing to move subtrees around with minumum effort.

Types of Binary Trees (Based on Structure)

  • Rooted binary tree: It has a root node and every node has atmost two children.
  • Full binary tree: It is a tree in which every node in the tree has either 0 or 2 children.
  • Perfect binary tree: It is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.
  • Complete binary tree: It is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
  • Balanced binary tree: A binary tree is height balanced if it satisfies the following constraints:
    • The left and right subtrees' heights differ by at most one, AND
    • The left subtree is balanced, AND
    • The right subtree is balanced
    • An empty tree is height balanced.
    • The height of a balanced binary tree is O(Log n) where n is number of nodes.
  • Degenarate tree: It is a tree is where each parent node has only one child node. It behaves like a linked list.

Binary Search Tree

A binary search tree is a useful data structure for fast addition and removal of data.

It is composed of nodes, which stores data and also links to upto two other child nodes. It is the relationship between the leaves linked to and the linking leaf, also known as the parent node, which makes the binary tree such an efficient data structure.

For a binary tree to be a binary search tree, the data of all the nodes in the left sub-tree of the root node should be less than the data of the root. The data of all the nodes in the right subtree of the root node should be greater than equal to the data of the root. As a result, the leaves on the farthest left of the tree have the lowest values, whereas the leaves on the right of the tree have the greatest values.

Insertion in a BST

To insert data into a binary tree involves a function searching for an unused node in the proper position in the tree in which to insert the key value. The insert function is generally a recursive function that continues moving down the levels of a binary tree until there is an unused leaf in a position which follows the following rules of placing nodes.

  • Compare data of the root node and element to be inserted.
  • If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree. Else,
  • Insert element as left child of current root.
  • If the data of the root node is greater, and if a right subtree exists, then repeat step 1 with root = root of right subtree.
  • Else, insert element as right child of current root.

Searching in a BST

The search function works in a similar fashion as insert. It will check if the key value of the current node is the value to be searched. If not, it should check to see if the value to be searched for is less than the value of the node, in which case it should be recursively called on the left child node, or if it is greater than the value of the node, it should be recursively called on the right child node.

  • Compare data of the root node and the value to be searched.
  • If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree. Else,
  • If the data of the root node is greater, and if a right subtree exists, then repeat step 1 with root = root of right subtree. Else,
    • If the value to be searched is equal to the data of root node, return true.
  • Else, return false.

Traversing in a BST

There are mainly three types of tree traversals:

Pre-order Traversal:

In this technique, we do the following :

  • Process data of root node.
  • First, traverse left subtree completely.
  • Then, traverse right subtree.

Post-order Traversal:

In this traversal technique we do the following:

  • First, traverse left subtree completely.
  • Then, traverse right subtree completely.
  • Then, process data of node.

In-order Traversal:

In in-order traversal, we do the following:

  • First process left subtree.
  • Then, process current root node.
  • Then, process right subtree.

READ More(From Src)