0

Level Order Traversal of Binary Tree

Problem statement:

Level order traversal for binary tree.

Example:

Level Order Traversal

 

Logic:

Basic idea behind level order traversal is explained in previous post on same topic. However, instead of using extra TreeNode as marker node to mark end of level, we will use ‘prevCount’ variable which will keep count for how many nodes we need to check if they have any child node in next level. For eg. for level 0, prevCount will be 1. So, we need to check for 1 node if there are any children. Number of children will be stored in ‘curCount’ variable. When prevCount is equal to 0, that means we finished checking for children of all the nodes at current level. Now prevCount will be curCount as for next level we need to check for curCount number of nodes. This idea will be more clear with below detail example for the above diagram.

  1. At start prevCount = 1,curCount = 0, and queue contains: <50>. We will repeat below steps while queue is not empty.
  2. Dequeue 5o, prevCount = 0, if left child of 50 present,curCount = 1 enqueue <35>, if right child of 50 present, curCount increment, curCount = 2, enqueue 57, queue <35,57>
  3. Now, prevCount is 0 means all nodes of current levels are traversed, so prevCount = nextLevel, in this example prevCount = 2 and curCount is updated to 0.
  4. Repeat step 2 and 3 till queue is not empty. prevCount =0, indicates that we finished traversing curCount and assigning curCount count to prevCount indicates how many nodes need to be traversed in next level.

 

Code:

Note:

This approach can be extended to perform level order traversal for k-ary tree. We can similarly keep  track of number of nodes at parent level and number of nodes need to be traversed in next level.

 

1

Level Order Traversal of Binary Tree

Problem: Level order traversal of binary tree.

eg.

Level Order Traversal

Logic:

In level order traversal nodes of tree are traversed level-wise from left to right. Like depth first traversals ( Inorder,preorder and postorder traversal) level order traversal is not easily implemented recursively because each node stores address of its left and right children.

Queue data structure is used to store nodes level wise so that  each node’s children are visited. How we are going to use queue then?

We will first add root in queue. We will use a marker node and when marker node present at the start of queue, all nodes at that level are completed. As at level 0 only root presents, add marker node after that. Now until queue does not contain only marker node we will repeat following steps:

1. De-queue node present at the start of queue.

2.Add children of that node in queue if present.

3. If at the start of queue marker node present, that means we completed visiting all nodes at previous node. So de-queue marker node from start and again en-queue it. En-queue marker node again to make sure that all nodes at this level are completely accessed.

4. If queue only contains marker node that means all children are traversed that means all nodes are traversed.

Implementation:

Complexity: As all nodes of tree are visited in traversal, time complexity is O(n).

0

Binary Search Tree

A binary tree is a Binary Search tree if and only if:

  • All values in left subtree of a node are less than value in node.
  • All values in right subtree of a node are greater than value in node.

For eg.

Binary Search tree

1.Insert value in a binary search tree:

While inserting a new value in a binary search tree only left or right subtree is traversed from root by comparing value of root with new value.

If new value is less than root then add it to the left subtree of root else add to right subtree of root. This can be done easily using recursion.

New node always inserted at the end of a existing tree, so while inserting number of nodes traversed depends on the height of a binary tree.

 2. Delete a value from binary search tree:

When a value is less than root then left subtree of root is traversed and if present, deleted from tree. If value to be deleted is greater than root, then right subtree of root is traversed and if present value is deleted.

If value to be deleted is present in tree then there are 3 possible scenarios:

1. Value present in a leaf node of a tree.

2. Node with that value has one child (either left or right).

3. Node with that value has both children.

If node to be deleted is a leaf node then we remove that node by assigning null value to the appropriate child pointer of its parent.

If that node has only one child then we replace that node with its existing child.

If node have both children, then we need to make sure that after deleting node, binary search tree properties are maintained. So to make sure that we can either select maximum value from left subtree of that node or select minimum value from right subtree of that node and replace it with node to be deleted.

If  value to be deleted is present in a leaf node or in worst case it does not present in a tree, in both cases number of nodes traversed in this case depends on a height of a tree.

3. Validate if given binary tree is binary search tree or not:

If for all the nodes in a binary tree, binary search tree constraints(Value in node always greater than values in its left subtree and value in a node always less than values in its right subtree)  are satisfied then that tree is a binary search tree.

Validating binary search tree can be done in a recursive way.  For each root value, we are checking if that value is in between range[min,max].  For root of a tree min value is Int Min value and max value is Int Max value.

For a node in a left subtree of a node, minimum value is a Int Min value but maximum value is value present in its parent. As we know,values in left subtree of a node always less than value in node in binary search tree.

For a node in a right subtree of a node, minimum value is a value present in its parent and maximum value is Int max. As we know, values in right subtree of a node are always greater than value in node in binary search tree.

While checking if tree is binary search tree or not, all nodes a tree are traversed so complexity is O(n).

0

Binary Trees

Lets discuss binary tree concepts and few basic frequently asked programming questions related to it.

Binary tree is tree in which each node can have at the most two children. This means each node can have 0 children (leaf node) , 1 children or two children. Generally referred as left child and right child. In terms, both left sub-tree and right sub-tree are also binary trees.

Complete Binary tree:  A binary tree in which all the levels are complete filled except last level which is filled from left to right.

Balanced Binary tree:  A binary tree in which difference between the height of left sub-tree and right sub-tree is 0 or 1

Perfect or Full Binary tree:  A binary tree in which each node have exactly 0 or 2 nodes.

A complete binary tree and a perfect binary tree is always going to be balanced binary tree.

Binary tree

 

Height of Binary tree: 

Lets consider ‘n’ total number of nodes in balanced binary tree and ‘lk‘ is the numbers nodes at level ‘l’.

So, for k = 0 -> l0 = 1  (root node)

for k = 1 -> l1  =  2 (second level)

for k = 2 -> l2  = 4  (second level) and so on..

This means each node will have twice number of nodes from its previous level. Total number of nodes can be represent using this concept as:

20  + 21 + 2 +2+2+……+ 2= n      here h is a height of tree

So,  2h+1   -1   = n           (for understanding, 20+1 -1 -> 21 – 1 =1 for level 0 and so on..for each level we can compute)

Now, we will calculate hight of balanced binary tree if has n nodes using above expression:

2h+1 = n+1

h+1 = lg(n+1)

h= lg(n+1) – 1

By l’Hopital’s rule this expression follows as:  lg(n+1) – 1 = lg(n)

So, h = lg(n)

 

In binary tree, a minimum height of tree for ‘n’ nodes can be |_lg(n)_|  (ceiling function) and maximum height can be (n-1).

A perfect binary tree of height h has 2leaf nodes in terms of height and has (n+1)/2 leaf nodes in terms of ‘n’.

Tree Traversal:

Traversal means visiting each node of a tree. Linear data structure like array, we traverse it in one direction starting from 0 index to last index of array. However, tree can be traversed in different ways.

Level Order Traversal: This is also known as breadth first traversal. Every node on a level before going to a lower level.

Depth First Traversal:  This traversal can be done in three ways, In-order, Pre-order and Post-order.

Inorder traversal: <left><root><right>

1. Traverse left sub tree.

2. Print data in root.

3. Traverse right sub tree.

Inorder traversal is used in binary search tree we get numbers sorted in sorted ascending order.

Preorder traversal: <root><left><right>

1. Print data in root.

2. Traverse left sub tree.

3. Traverse right sub tree.

By using preorder traversal  we can make a copy of a tree.

Postorder traversal: <left><right><root>

1. Traverse left sub tree.

2. Traverse right sub tree.

3. Print data in root.

Postorder traversal is used when we want to delete a tree as we visit parent node after visiting its children.

Tree traversal

Note: To remember traversals simple method is to remember position of root with respect to prefix of name of traversal.

Implementation of traversals:

Inorder traversal:

Preorder traversal:

Postorder traversal:

In each traversal every node of a tree is visited so time complexity  for tree traversal in O(n).

 

You can find more coding questions and solutions here.

Lets discuss about binary search tree in next session..

0

Trees

Hi guys, today I am going to discuss trees. We are going to discuss basic concepts of tree data structure before we start discussion about binary trees.

Tree:

Tree is a abstract data structure used to stored data in hierarchical order.

In simple words imagine a diagram showing family members of your  family showing relationships like parent-children, grandparents. This diagram is in term a ‘tree data structure’.  As you can imagine, its difficult to maintain such type of orders in linear data structure (array, linked list etc.) tree data structure is require.

Basic difference between graph and tree is there are no loops or circles in trees, so each element (referred as node)  of tree can be accessed by accessing unique path.

Tree is defined as a binary tree, ternary tree …k-ary depending on maximum number of children a parent element can have.

Tree Terminology:

Root: The topmost node of a tree with no parent.

Leaf Node:  Nodes of tree with no children.

Path: Sequence of nodes connected with edges.

Length of path: Number of edges connecting nodes between that path.

Height of node: Longest path from node that node to leaves.

Height of tree:  Longest path from root and a leaf.

Depth of node: Distance(number of edges) of that node from root. So for ‘root’ depth=0

and height can be considered as maximum depth of all nodes.

Degree of node: Number of direct children of that node.

Considering these tree terminologies one can say:

-In tree each node can have at the most one parent.

-Each node can be traversed from a root node.

-Each node of a tree can be considered a sub-tree. This property of trees is used to implement trees recursively.

tree

Lets discuss about binary trees in next session…