Binary Tree

A binary tree is a tree where every node has two or fewer children. The children are usually called left and right. (bad name given kids, how will you the left guy to go on right). Every node contains some data that we call a key.

Few guide line normally we follow while building binary trees

A binary search tree is a binary tree in which every node contains a key that satisfies following criteria:

  • The key in left child is less than the key in the parent node
  • The key in the right child is more than the parent node
  • The left and right child are again binary search trees.
When a Node has only one child, then it is condsidered as the other child is Null. If a Node has no childern(Leaf) then the node has left and right child value as Null.

Binary tree traversals

  • PreOrder traversal : In PreOrder traversal,each node is processed before either of its sub-trees.In simpler words,Visit each node before its children.
  • InOrder traversal : In InOrder traversal,each node is processed between subtrees.In simpler words,Visit left subtree, node and then right subtree.
  • PostOrder traversal : In PostOrder traversal,each node is processed after subtrees traversal.In simpler words,Visit left subtree, right subtree and then node.
  • Level order traversal : In Level order traversal, tree is traversed by each level. It is same as breadth first search.
  • Spiral/Zigzag order traversal : In spiral order traversal, tree is traversed in spiral shape.
  • Binary tree reverse level order traversal: It is similar to level order but in reverse
  • Binary tree boundary traversal : This traversal traverse boundary of binary tree

Types of Binary Tree

Full Binary Tree

When every node of the Binary tree has two(2) or zero(0) children then we call it as Full Binary Tree. Both types of nodes can appear at all levels in the tree.

An example is given in the following figure. full-binary-tree-kotlin

Complete Binary Tree

A complete binary tree is formed when every level of the tree is completely filled, except possibly from the last level. Also, the last level has all nodes as left as possible. complete-binary-trees-kotlin

Perfect Binary Tree

We get a perfect binary tree when all tree internal nodes have two children, as well as all leaves, are uniformed by having the same depth. perfect-binary-tree-kotlin

In Perfect Binary Tree, the number of total nodes on each "level" doubles as we move down the tree.

Balanced Binary Tree

We can call a binary tree as Balanced Binary tree when the difference between the height of left and right subtree for every node is not more than 1

The height is, number of nodes present from the leaf to the given node. The height always starts with 0, when there is only root then the height of the tree is 0. If the tree is empty the height of the tree is -1

Be careful, when you you are calculating the height. Denoted the height difference in the image height-difference-balanced-kotlin height-of-balanced-binary-tree-kotlin

Below tree satisfies the Balanced tree conditions balanced-binary-tree-kotlin

Below tree doesnot satisfy the Balanced tree condition not-balanced-binary-tree-kotlin

About Author

This article is written by Pavan, who is serving notice period in an MNC, Bangalore. He thought, let the articles speak rather than his image. He is also the same person who created the reporter for Protractor Jasmine

Share this Article Facebook
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions