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

Basic operations on Singly Linked List

We will discuss basic operations on singly linked list. Operations like insert,delete and print.

1. Insert:

In singly linked list, last node stores next address value as null. So while inserting new node , linked list is traversed from start to end.

New node will be inserted at the end so last node’s next address will be pointed to new node.

As all nodes are visited while inserting new value, time complexity for this operation is O(n).

2. Insert at specific position:

Given a value and position where you want to insert. First traverse through linked list until we get node previous to desired position and then insert node at that position. In this problem we also need to check if given position is out of range of given linked list. For example, currently linked list contains only 4 nodes and for new value position is given as 10, which is incorrect.

In this case best case is insert value at start, for this time complexity will be O(1) and worst case is insert at last position or position is out of range, in this scenario all nodes of linked list will be traversed so time complexity will be O(n).

3. Delete node from at specific position:

Given position at which you want to delete a node . First traverse through linked list until we get node previous to desired position and then delete node at that position. In this problem we also need to check if given position is out of range of given linked list. For example, currently linked list contains only 4 nodes and position is given as 10, which is incorrect.

In this case best case is delete node at position 0 which is head of linked list , for this time complexity will be O(1) and worst case is delete  last node or position is out of range, in this scenario all nodes of linked list will be traversed so time complexity will be O(n).

4. Print all linked list values:

This is a simple operation on a linked list.

As all nodes are visited to print values, time complexity of this operation is O(n).

You can find solution to more problem on linked list here.

0

Linked List

Linked list is a data structure used to store data in linear order.

We know array , data structure which is used to store data in linear order, then why we need another data structure for same??

Answer to this question highlights main difference between array and linked list. For an array, data always stored in a continuous memory locations. so if I declare array of size 10, depending on size of data type * 10 memory block is reserved for array elements.

However for linked list, no continuous memory allocation is required. In linked list each element stores a data and pointer to (address of) the next element. So no continuous memory allocation require to store data. Each of this structure containing data and address is referred as ‘Node’.

The first element of linked list always referred as ‘Head’ and last node has address as ‘null’.

So what are the advantages and disadvantages of linked list compared to array?

Advantages:

1. Linked list is a dynamic data structure means the number of nodes in a list is not fixed and can grow and shrink on demand. Memory allocation is done when program is running.

2. Insertion and deletion operation is easy  to implement compared to array.

3. They can reduce access time and may expand in real time without memory overhead.

 

Disadvantages:

1. Linked list requires more memory space to store reference of next node.

2. Linked list provides sequential access which means linked list accessed from head. So it is not possible to get element at specific location directly.

3. Time require to access individual element is more.

4. It is difficult to reverse traverse linked list as compared to arrays.

 

There are three variations in linked list as follows:

1. Singly linked list:  This is a basic linked list which is described above. Each node contains pointer to the next element is list.

Singly linked list

2. Doubly Linked List: In this list each element store pointer to the next element and a previous element.  So for head node previous pointer value is Null and for last node pointer to next element is stored as Null.

Doubly linked list

3. Circular Linked List: This linked list is like a singly linked list only difference is last node of linked list store pointer of head.

Circular linked list

 

We will discuss basic operations like insert, delete, traverse on each type of  linked list in next session..

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..