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-examples-kotlin

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

aaaaaaaaaaaaa
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group