Binary Tree

Introduction to Trees

A Tree is a hierarchical data structure that is different from linear data structures like arrays, linked lists, stacks, and queues. A subtree is a part of the tree below any chosen node that can be considered as a separate tree with that node as a root node. Subtree is very much similar to the sub-directory which lies inside of a root directory as in our computer systems.

  • A Binary Tree is a type of tree in which each node cannot have more than 2 children nodes. These types of trees are very important and are used extensively.
  • The root node of a Binary Tree is the top-most node from where the tree hierarchy begins.
  • Leaf nodes are those nodes that lie at the terminal part of the tree indicating the last or bottom-most part of the tree.
  • Children of a node are the nodes to which the pointers from the node directly point. These nodes lie directly below or in the next hierarchical level of the chosen node.
  • The ancestors of a given node are all the nodes that come before the node while traversing from the root node to the given node.

There are different types of Binary Trees:

  1. Full Binary Tree – It is a type of tree in which each node has either 0 or 2 children.

2. Complete Binary Tree – It is a type of tree where all the levels of the tree are filled with nodes except the last level. The last level must have each node as left as possible.

3. Perfect Binary Tree – It is a type of tree in which all the leaf nodes should be on the same level.

4. Balanced Binary Tree – In a balanced binary tree, the height of the tree should be at max log(N), where N is the number of nodes. The tree should not be skewed.

5. Degenerate Tree – A degenerate tree is a skewed tree that is similar to a linked list where each node is connected to the left of the previous node and the tree goes leftwards only.

Say, for N = 4, the degenerate tree would look like this:

Special thanks to Priyanshi Goel for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article