Trees

A tree is a non-linear, linked, hierarchical data structure. It is a collection of nodes, and each node contains some data with references to other nodes. The first node of a tree is called the root node because it can never have a parent node. Here is a diagram displaying the basic terminology of a tree:

The circles in the above image are nodes and they contain some data, and they are also connected to other nodes. The node labelled 1 is the root node and it has two child nodes 2 and 3. Nodes 2 and 3 are also parent nodes to nodes 4 & 5 and 6 respectively. The last nodes of a tree are called leaf nodes, which in our example are nodes 7 & 8.

A tree is constructed of many subtrees and each node can have a left subtree and a right subtree.

Binary Trees

More often than not we will require the use of binary trees, which are a special kind of tree where each node can have at most 2 children. A binary tree is made of three components: the data, a pointer to the left child node, and a pointer to the right child node.

Here’s what a node class looks like

class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
      this.data = data;
      this.left = null;
      this.right = null;
    }
  }

The data is whatever we want to store in the node while the left and right variables are references to child nodes. The above class is very similar to a doubly linked list class.

Height of Binary Trees

The height of a binary tree is equal to the largest number of edges from the root to the most distant leaf node

Types of Binary Trees

1. Full Binary Tree

A full binary tree is the kind of binary tree where every node has either two children or no children at all.

2. Complete Binary Tree

A complete binary tree is a full binary tree except that the leaf nodes can have one child node. And this child node should reside on the left side.

3. Perfect Binary Tree

A binary tree is said to be perfect if every node has strictly two children and every leaf node is at the same level.

4. Balanced Binary Tree

A balanced binary tree is a type of tree in which every node’s left and right subtree differ by no more than 1.

5. Degenerate Binary Tree

In a degenerate binary tree, every internal node has only a single child. This tree then becomes similar to a linked list.

Binary Search Trees

A Binary Search Tree is a special kind of binary tree in which the value of all the nodes to the left of the root node is less than the value of the root node while the value of all the nodes to the right of the root node is greater than the value of the root node.

Binary search trees are highly efficient when we need to perform search operation as it reduces the time taken to find any element.

Generally, the time complexity of BST is O(H) where ‘H’ is the height of the tree.

Applications of Binary Trees

• Binary trees are generally used when we need to store data in a hierarchical way such as in a file system on a computer.
• They are also used in Binary Space Partitioning(BSP) and implementation of Hash trees, Syntax trees, etc.