Sep 092017

Given a pointer to the root node of the tree, write code to find if it is an Almost Complete Binary Tree or not?

A Binary Tree of depth d is Almost Complete iff:

  1. The tree is Complete Binary Tree (All nodes) till level (d-1).
  2. At level d, (i.e the last level), if a Node is present, then all the Nodes to the left of that node should also be present.

For example, the left tree below is NOT an Almost Complete Binary Tree but the right tree is an Almost Complete Binary Tree

    NOT Almost Complete           Almost Complete Binary Tree
   --------------------           ---------------------------
          _ A _           |             _ A _
        /       \         |           /       \
       B         C        |          B         C
     /   \     /   \      |        /   \     /   \
    D     E    F    G     |       D     E    F    G
   / \        / \         |      / \ 
  H   I      J   K        |     H   I

The left tree is not almost complete because in the last level, the nodes left to Node-J are missing (children of Node-E).
Continue reading »

May 032017

The structure of Node of a Binary Tree and Doubly linked list are same.

struct Node
   int data;
   Node* left;
   Node* right; 

 Structure of Node of a Binary Tree    

struct Node
   int data;
   Node* previous;
   Node* next; 

  Structure of Node of a Doubly linked list

If we treat left pointer as previous and right pointer as next, we can use the Node of a Binary Tree to represent node of a Doubly linked list or vice-versa.

Given a binary tree, modify the pointers in each node of the tree so that they represent a Doubly linked. Order of the nodes in DLL should be same as that in the in-order traversal.

If the Input Binary tree is as below

Binary Search Tree

then the function should modify pointers in the nodes, as shown below and return the head pointer.

Doubly Linked List
Continue reading »

Apr 262017

Given a Binary tree, write code to find the length of longest path such that value of node in that path are consecutive and in decreasing order. For example is the tree is

Then output should be: 3 because path (5, 4, 3) has all nodes in consecutively decreasing order.

Note that Path <5, 6, 7> are also consecutive, but they are not in decreasing order, hence not considered. Continue reading »

Jan 312017

Given a Binary Tree and a Node, Write a function that return the vertical distance of that node from root of the tree. The vertical distance of a node is computed as below:

  • Then the vertical distance of root is 0.
  • The vertical distance of right node is distance of root+1.
  • The vertical distance of left node is distance of root-1.

For example, if the binary tree is as given below:

Then vertical distance of Node-B from root is -1. E is at a vertical distance 0 from the root (we move one step left and then one step right, hence the net vertical distance from root is zero). Continue reading »

Jun 192016

Binary heap is used to implement Priority queue. It is an array object, visualized as an almost complete binary tree. Binary heap comes in two flavours

  • Max-Heap
  • Min-Heap

A max-heap is an almost complete binary tree, where, value at each node is greater than the value of its children. Similarly, a min-heap is an almost complete binary tree where value at a node is less than both its children (unless it is a leaf node and does not have any children).

Continue reading »

Jun 242015

One way to ask this question is:

Given a Binary tree that represent a family hierarchy. A parent can have at most two children (at most one girl child and at most one boy child). A girl child (if present) is always represented as left child in the binary tree, and a boy child (if present) is always represented as the right child. There will never be a situation that a parent has 2 girl children or 2 boy children or have more then 2 children. Find the total number of girls in the family.

Another way to ask the same question is to directly ask,

Write a function that returns total number of left node in a binary tree.

For example, Given the below binary tree, there are four girl children (B, D, H and F):


The catch in twisting the question ( as girl-child in family) is to see if you can make sense from ambiguous problems. Also, sometimes, in our code, we skip the check for left child of the right child (which need to be counted).


The solution is fairly simple. We traverse the entire tree, and if a node has left child then we increment the number of girl children by one, else not.


1. If root is NULL, then return 0.
2. If root does not have Left child 
    - Return the number of left children in right-subtree.
3. Add the left children inside left and right subtree
   add 1 to it for the left-child of root 
   and return the total sum 


int countLeftChild(Node* r)
    if(r==NULL){ return 0; }
    if(r->lptr == NULL)
        // NO Left child.
        return countLeftChild(r->rptr);
        // Left child present.
        return countLeftChild(r->lptr) + countLeftChild(r->rptr) + 1;