Tree Recovery

The Problem

Given the preorder and inorder traversal of a tree write the postorder traversal of the tree.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Collections;

namespace ConsoleApplication1

{

    class Program

    {

        static string answer = "";

        static void Main(string[] args)

        {

            string preord = "12345678";

            string inord = "32541876";

            former(preord, inord, false);

            while(s.Count>0)

            {

                answer = answer + s.Pop();

            }

            Console.WriteLine(answer);

        }

        static Stack s = new Stack();

        static void former(string preord, string inord, bool control)       

        {

            if (inord.Length == 1 || inord.Length < 1)

            {

                if (inord.Length == 1)

                {

                    answer = answer + inord;

                    if (control == true)

                    {

                        answer = answer + s.Pop();

                    }

                    return;

                }

                else

                {

                    if (control == true)

                    {

                        answer = answer + s.Pop();

                    }

                    return;

                }

            }

            else

            {

                int i=0, j=0;

                for (i = 0; i < preord.Length; i++)

                {

                    bool flag = false;

                    for (j = 0; j < inord.Length; j++)

                    {

                        if (preord[i] == inord[j])

                        {

                            flag = true;

                            break;

                        }

                    }

                    if(flag == true)

                    {break;}

                }

                string s3 = inord;

                string s4 = preord;

                //Left sub-tree in the inorder traversal.

                string s2 = inord.Remove(j, inord.Length - j);

                //Left sub-tree in the preorder traversal.

                string s1 = preord.Substring(i + 1, s2.Length);

                //Right sub-tree in the inorder traversal.

                string s5 = s3.Remove(0, j + 1);

                int index = s4.IndexOf(s1, 0);

                //Right sub-tree in the preorder traversal.

                string s6 = s4.Remove(index, s1.Length);

                //Push the root into the stack.

                s.Push(s6[0]);

                //Right sub-tree without the root in the preorder traversal.

                s6 = s6.Remove(0, 1);

                control = false;

                former(s1, s2, control);

                control = true;

                former(s6, s5, control);

            }

        }

    }

}

Given a binary tree output should have the node values as sum of all the children data and its node data

Input tree:                  Output tree:

C++ Program:

#include<iostream>
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 return new_node;
}

void postorder(struct node* root)
{
 if(root)
 {
     postorder(root->left);
     postorder(root->right);
     if(root->left)
     {
         root->data=root->data+root->left->data;
     }
     if(root->right)
     {
         root->data=root->data+root->right->data;
     }
 }
}

int height(struct node* root)
{
 if(root==NULL)
 {
  return 0;
 }
 else
 {
  int lheight=1+height(root->left);
  int rheight=1+height(root->right);
  return lheight>rheight?lheight:rheight;
 }
}

void levelorderprint(struct node* root,int level)
{
 if(root && level==0)
 {
  cout<<root->data<<" ";
 }
 else if(root)
 {
  levelorderprint(root->left,level-1);
  levelorderprint(root->right,level-1);
 }
}

void levelorder(struct node* root)
{
 int h=height(root);
 for(int i=0;i<h;i++)
 {
  levelorderprint(root,i);
  cout<<endl;
 }
}

int main()
{
        struct node* root1=createnode(1);
 root1->left=createnode(2);
 root1->right=createnode(3);
 root1->left->right=createnode(5);
 root1->left->left=createnode(4);
 root1->right->right=createnode(7);
 root1->right->left=createnode(6);
 //root1->right->right->left=createnode(8);
 cout<<"The input tree is:\n";
 levelorder(root1);
 postorder(root1);
 cout<<"The sum tree is\n";
 levelorder(root1);
}
Output:
The input tree is:
1
2 3
4 5 6 7
The sum tree is
28
11 16
4 5 6 7

Process returned 0 (0x0)   execution time : 0.016 s
Press any key to continue.

C++ Program for Tree Iterator

Problem

Given n-ary (n children per node) tree, write a C++ iterator to iterate over all the nodes.

Solution

Iterator Interface

One of the potential interface is as follows:

/**
 * If there are more children to be traversed in the current layer
 * @param index
 * @return True if there are children yet to be traversed, false otherwise
 */
virtual bool hasMoreChildren(int index);

/**
 * Move to child at index in a layer
 * @param index
 */
virtual void moveToChildAt(int index);

/**
 * Print the current node
 * @param index
 */
virtual void printNode();

Implementation

For implementing the iterator, we will use a stack to keep track of the node being traversed in the tree.

private:
    Node* mCurrentNode = nullptr;
    std::stack<Node*> mNodeStack;
};

The mCurrentNode and mNodeStack are used in the implementation as follows:

C++ Code

bool TreeIterator::hasMoreChildren(int index) {
    if (mNodeStack.empty()) return false;
    mCurrentNode = mNodeStack.top();
    // If no children, return false.
    if (mCurrentNode->children().empty()) {
        mNodeStack.pop();
        if (!mNodeStack.empty()) {
            mCurrentNode = mNodeStack.top();
        }
        return false;
    }
    auto it = mCurrentNode->children().begin();
    it += index;
    // If all children in this layer are traversed, return false.
    if (it == mCurrentNode->children().end()) {
        mNodeStack.pop();
        if (!mNodeStack.empty()) {
            mCurrentNode = mNodeStack.top();
        }
        return false;
    }
    // There are more children to be drawn, return true
    return true;
}

void TreeIterator::moveToChildAt(int index) {
    if (mCurrentNode->children().empty()) {
        // No children, nothing to do in current layer
        return;
    }
    auto it = mCurrentNode->children().begin();
    it += index;
    if (it == mCurrentNode->children().end()) {
        // All children visited once, nothing to do in current layer
        return;
    }
    mNodeStack.push(*it);
    mCurrentNode = mNodeStack.top();
}

void TreeIterator::printNode() {
    cout << mCurrentNode->data() << endl;
}

Using the iterator

/**
 * Recursively traverse the tree hierarchy
 */
void traverse() {
    int i = 0;
    while (hasChildren(i)) {
        moveToChildAt(i);
        traverse();
        i++;
    }
}

int main() {
    TreeIterator *it;
    it->traverse();
}

Explanation

The above code is a recursively traverses the children of each node in the tree. The stack maintains the current node at the top and the index passed from the traverse() method determines how many children of a particular node have been visited.

Alternate Solutions

Alternate solutions may use the following approach.

Visitor Pattern

Yet to write a working code, but this approach would mark a node as visited once it has been traversed to keep track of which child of a particular node should be visited next.

Parent Tracking

This requires modifying the tree node to contain a pointer to the parent node so that the mCurrentNode can be moved to the parent when all the children of a particular node are visited.

Right Neighbour of nodes in a Binary Tree

Given a binary tree with nodes that have left, right pointers pointing to the left and right children respoectively. Each node also has a right-neighbor pointer that currently points to null.
Write a function to make it point to its neighbor.

Example:
Input tree
1
2 3
4 5 6 7
Expected configuration of the tree
1 right-neighbour should point to null
2 right-neighbour should point to 3
3 right-neighbour should point to null
4 right-neighbour should point to 5
5 right-neighbour should point to 6
6 right-neighbour should point to 7
7 right-neighbour should point to null

Approach
1. Do a level-order traversal of the binary tree.
2. During this traversal keep track of the current root you visit in a level.
3. The next time you visit a root in the same level, make the right-neighbour pointer of the current root to point to this root.
4. Update the current pointer to this root.

#include<iostream>
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
 struct node* right_neighbour;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 new_node->right_neighbour=NULL;
 return new_node;
}

int height(struct node* root)
{
 if(root==NULL)
 {
  return 0;
 }
 else
 {
  int lheight=1+height(root->left);
  int rheight=1+height(root->right);
  return lheight>rheight?lheight:rheight;
 }
}

void levelorderprint(struct node* root,int level,struct node** current)
{
 if(root && level==0)
 {
  cout<<root->data<<" ";
  if(*current == NULL)
  {
      *current = root;
  }
  else
  {
      (*current)->right_neighbour=root;
      *current=root;
  }
 }
 else if(root)
 {
  levelorderprint(root->left,level-1,current);
  levelorderprint(root->right,level-1,current);
 }
}
void levelorder(struct node* root)
{
 int h=height(root);
 struct node* addr=NULL;
 struct node** current=&addr;
 for(int i=0;i<h;i++)
 {
     addr=NULL;//Very important step because addr gets changed in the function levelorderprint as its address is passed.
     current=&addr;
     levelorderprint(root,i,current);
     cout<<endl;
 }
}

void inorder(struct node* root)
{
        if(root)
 {
  inorder(root->left);
  cout<<root->data;
  if(!root->right_neighbour)
  {
      cout<<endl;
  }
  else
  {
      cout<<"->"<<root->right_neighbour->data<<endl;
  }
  inorder(root->right);
 }
}

int main()
{
    struct node* root1=createnode(1);
    root1->left=createnode(2);
    root1->right=createnode(3);
    root1->left->right=createnode(5);
    root1->left->left=createnode(4);
    root1->right->right=createnode(7);
    root1->right->left=createnode(6);
    root1->right->right->left=createnode(8);
    cout<<"The input tree is\n";
    levelorder(root1);
    cout<<"The right neighbours are:\n";
    inorder(root1);
}
Output:
1
2 3
4 5 6 7
8
The right neighbours are:
4->5
2->3
5->6
1
6->7
3
8
7

Process returned 0 (0x0)   execution time : 0.056 s
Press any key to continue.

Given a binary tree find out whether the left and right sub-trees are mirror images of each other

#include<stdio.h>
#include<stdlib.h>
 
struct node
{
        int data;
        struct node* left;
        struct node* right;
};
struct node* createnode(int x)
{
        struct node* new_node=(struct node*)malloc(sizeof(struct node*));
        new_node->data=x;
        new_node->left=NULL;
        new_node->right=NULL;
        return new_node;
}
 
int isMirror(struct node* node1, struct node* node2)
{
        if(node1 == NULL && node2 != NULL)
        {
                return 0;
        }
        else if(node1 != NULL && node2 == NULL)
        {
                return 0;
        }
        else if(node1 == NULL && node2 == NULL)
        {
        		return 1;
        }
        else if(node1->data != node2->data)
        {
                return 0;
        }
        return isMirror(node1->left, node2->right) && isMirror(node1->right, node2->left);
}
 
 
int height(struct node* root)
{
        if(root==NULL)
        {
                return 0;
        }
        else
        {
                int lheight=1+height(root->left);
                int rheight=1+height(root->right);
                return lheight>rheight?lheight:rheight;
        }
}
 
void levelorderprint(struct node* root,int level)
{
        if(root && level==0)
        {
                printf("%d ",root->data);
        }
        else if(root)
        {
                levelorderprint(root->left,level-1);
                levelorderprint(root->right,level-1);
        }
}
 
void levelorder(struct node* root)
{
        int h=height(root);
        for(int i=0;i<h;i++)
        {
                levelorderprint(root,i);
                printf("\n");
        }
}
 
int main()
{
        struct node* root1=createnode(1);
        root1->left=createnode(2);
        root1->right=createnode(2);
        root1->left->right=createnode(4);
        root1->left->left=createnode(3);
        root1->right->right=createnode(3);
        root1->right->left=createnode(4);
        //root1->right->right->left=createnode(8);
        printf("The input tree is:\n");
        levelorder(root1);
        int result = 0;
        result = isMirror(root1, root1);
        if(result == 1)
        {
                printf("The left and right subtrees are mirror images\n");
        }
        else
        {
                printf("The left and right subtrees are not mirror images\n");
        }
        return 0;
}

Vertical Order Traversal of Tree

Java Program using HashMap:

public class TreeTraversalPrograms {
    private static Map<Integer, List<TreeNode>> treeNodeVerticalLevelMap = new TreeMap<>();

    public static void main(String[] args) {
        // Tree construction
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.right.left.right = new TreeNode(8);
        root.right.right.right = new TreeNode(9);

        verticalOrderTraversal(root, 0);
        SortedSet<Integer> keys = new TreeSet<Integer>(treeNodeVerticalLevelMap.keySet());
        for (Integer key : keys) {
            List<TreeNode> treeNodesList = treeNodeVerticalLevelMap.get(key);
            for (TreeNode treeNode : treeNodesList) {
                System.out.print(treeNode.data + ",");
            }
            System.out.println();
        }
    }
    public static void verticalOrderTraversal(TreeNode node, int width) {
        if (node == null) {
            return;
        }
        if (treeNodeVerticalLevelMap.containsKey(width)) {
            List<TreeNode> treeNodesList = treeNodeVerticalLevelMap.get(width);
            treeNodesList.add(node);
            treeNodeVerticalLevelMap.put(width, treeNodesList);
        } else {
            List<TreeNode> treeNodesList = new ArrayList<>();
            treeNodesList.add(node);
            treeNodeVerticalLevelMap.put(width, treeNodesList);
        }
        if (node.left != null) {
            verticalOrderTraversal(node.left, width - 1);
        }
        if (node.right != null) {
            verticalOrderTraversal(node.right, width + 1);
        }
    }
}

Sample Output:

4,
2,
1,5,6,
3,8,
7,
9,

Non-recursive level order traversal of a binary tree

Java Code:

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
   
    public TreeNode() {
       
    }
   
    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

//Non-recursive LevelOrder Traversal
    public String levelOrderTraversal(TreeNode node) {
        StringBuilder traversal = new StringBuilder();
        if(node == null) {
            return traversal.toString();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        int thisLevel = 1;
        int nextLevel = 0;
        while(!queue.isEmpty()) {
            for(int i=0; i<thisLevel; i++) {
                node = queue.remove();
                traversal.append(node.data);
                if(node.left != null && node.right != null) {
                    nextLevel += 2;
                    queue.add(node.left);
                    queue.add(node.right);
                }
                else if(node.left != null || node.right != null) {
                    nextLevel += 1;
                    if(node.left != null) {
                        queue.add(node.left);
                    }
                    else {
                        queue.add(node.right);
                    }
                }
            }
            thisLevel = nextLevel;
            nextLevel = 0;
        }
        return traversal.toString();
    }

Unit Tests:

public class TreeProgramsTest {

    TreeNode root;
    @Before
    public void initialize() {
        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
    }

    @Test
    public void testLevelOrderTraversal() {
        TreeTraversalPrograms treeTraversalPrograms = new TreeTraversalPrograms();
        Assert.assertTrue(treeTraversalPrograms.levelOrderTraversal(root).equals("123456"));
    }
}

Find the Largest Sum Path from root to leaf in a binary tree

#include<iostream>
#define SMALL -999999
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
 struct node* parent;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 new_node->parent=NULL;
 return new_node;
}
void parentfinder(node *root,node *parent)
{
    if(root)
    {
        root->parent=parent;
        parent=root;
        parentfinder(root->left,parent);
        parentfinder(root->right,parent);
    }
    return;
}
int height(struct node* root)
{
 if(root==NULL)
 {
  return 0;
 }
 else
 {
  int lheight=1+height(root->left);
  int rheight=1+height(root->right);
  return lheight>rheight?lheight:rheight;
 }
}
void levelorderprint(struct node* root,int level)
{
 if(root && level==0)
 {
  cout<<root->data<<"->";
  if(root->parent)
  {
      cout<<root->parent->data<<endl;
  }
 }
 else if(root)
 {
  levelorderprint(root->left,level-1);
  levelorderprint(root->right,level-1);
 }
}
void levelorder(struct node* root)
{
 int h=height(root);
 for(int i=0;i<h;i++)
 {
  levelorderprint(root,i);
  cout<<endl;
 }
}
struct node** summer(node *root,node **maximum,node *parent)
{
    if(root)
    {
        if(parent)
        {
            root->data=root->data+parent->data;
            if((*maximum)->data<root->data)
            {
                *maximum=root;
            }
        }
        parent=root;
        summer(root->left,maximum,parent);
        summer(root->right,maximum,parent);
    }
    return maximum;
}
int searchformax(node *root,node **max,bool *found,int A[100])
{
    static int i=0;
    if(root)
    {
        if(root==*max)
        {
            *found=true;
        }
        if(!(*found))
        {
            searchformax(root->left,max,found,A);
            if(!(*found))
            {
                searchformax(root->right,max,found,A);
            }
        }
        if(*found)
        {
            A[i]=root->data;
            i++;
        }
    }
    return i;
}
int main()
{
    struct node* root=createnode(1);
 root->left=createnode(2);
 root->right=createnode(3);
 root->left->right=createnode(4);
 root->left->left=createnode(5);
 root->right->right=createnode(-6);
 root->right->left=createnode(7);
 root->right->right->left=createnode(8);
 //root->right->right->left->left=createnode(10);
 root->right->right->right=createnode(10);
 parentfinder(root,NULL);
 levelorder(root);
 node *ptr=new struct node;
 ptr->data=SMALL;
 node **max=&ptr;
 max = summer(root,max,NULL);
 bool var=false;
 bool *found = &var;
 int A[100];
 int count=searchformax(root,max,found,A);
 for(int i=0;i<count-1;i++)
 {
     A[i]=A[i]-A[i+1];
 }
 cout<<"The path is:"<<endl;
 while(count--)
 {
     cout<<A[count]<<endl;
 }
}
Output:
1->
2->1
3->1

5->2
4->2
7->3
-6->3

8->-6
10->-6

The maximum sum path is:
1
3
7

Given a sorted array, convert it into a balanced binary search tree

#include<iostream>
using namespace std;

struct node
{
	int data;
	struct node* left;
	struct node* right;
};
struct node* createnode(int x)
{
	struct node* new_node=new struct node;
	new_node->data=x;
	new_node->left=NULL;
	new_node->right=NULL;
	return new_node;
}
int height(struct node* root)
{
	if(root==NULL)
	{
		return 0;
	}
	else
	{
		int lheight=1+height(root->left);
		int rheight=1+height(root->right);
		return lheight>rheight?lheight:rheight;
	}
}
struct node* createBST(int *A, int low, int high)
{
    if(low>high)
    {
        return NULL;
    }
    else
    {
        int mid = (low + high)/2;
        struct node* root = createnode(A[mid]);
        root->left = createBST(A, low, mid - 1);
        root->right = createBST(A, mid + 1, high);
        return root;
    }
}
void levelorderprint(struct node* root,int level)
{
	if(root && level==0)
	{
		cout<<root->data<<" ";
	}
	else if(root)
	{
		levelorderprint(root->left,level-1);
		levelorderprint(root->right,level-1);
	}
}
void levelorder(struct node* root)
{
	int h=height(root);
	for(int i=0;i<h;i++)
	{
		levelorderprint(root,i);
		cout<<endl;
	}
}
int main()
{
    int A[6] = {1,2,3,4,5,6};
    int n = 5;
    struct node* treeRoot = createBST(A,0,n-1);
    levelorder(treeRoot);
}

Printing all nodes at a given distance from a starting node in a binary tree

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* createnode(int x)
{
    struct node* new_node=new struct node;
    new_node->data=x;
    new_node->left=NULL;
    new_node->right=NULL;
    return new_node;
};
int printKDistance(node* root,node* start,int k,int *found)
{
    if(root)
    {
        //cout<<root->data<<endl;
        if(k==0)
        {
            cout<<root->data<<endl;
        }
        else if(root==start || *found==1)
        {
            *found=1;
            printKDistance(root->left,start,k-1,found);
            printKDistance(root->right,start,k-1,found);
            return 1;
        }
        else if(*found==0)
        {
            int ldist = printKDistance(root->left,start,k,found);
            //cout<<"ldist="<<ldist<<endl;
            int rdist=0;
            if(*found==0)
            {
                rdist = printKDistance(root->right,start,k,found);
            }
            if((ldist == k || rdist == k) && *found==1)
            {
                cout<<root->data<<endl;
            }
            else
            {
                if(ldist!=0 || rdist!=0)
                return ldist>rdist?1+ldist:1+rdist;
            }
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return 0;
    }
}
int main()
{
    struct node* root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->right=createnode(4);
    root->left->left=createnode(5);
    root->right->right=createnode(6);
    root->right->left=createnode(7);
    root->right->right->left=createnode(8);
    //root->right->right->left->left=createnode(10);
    root->right->right->right=createnode(10);
    int k=2;
    //struct node* start = root->right->right->left;
    struct node* start = root->right->left;
    cout<<"start node="<<start->data<<endl;
    cout<<"k="<<k<<endl;
    int a=0;
    int *found=&a;
    printKDistance(root,start,k,found);
}
Output:
start node=7
k=2
Node: 1

Finding the Lowest Common Ancestor of two given nodes in a Binary Tree

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* left;
    struct node* right;
    struct node* next;
};
struct node* createnode(int x)
{
    struct node* new_node=new struct node;
    new_node->data=x;
    new_node->left=NULL;
    new_node->right=NULL;
    new_node->next=NULL;
    return new_node;
};
int help_anc(struct node* root,node* n1,node* n2)
{
    if(root)
    {
        if(root==n1)
        {
            return 1;
        }
        else if(root==n2)
        {
            return 1;
        }
        else
        {
            return help_anc(root->left,n1,n2)+help_anc(root->right,n1,n2);
        }
    }
    else
    {
        return 0;
    }
}
struct node* Ancestor(node* root,node* n1,node* n2)
{
    if(root)
    {
        int lf = help_anc(root->left,n1,n2);
        int rf = help_anc(root->right,n1,n2);
        if(lf==1 && rf==1)
        {
            return root;
        }
        else
        {
            node* lca = Ancestor(root->left,n1,n2);
            if(lca!=NULL)
            {
                return lca;
            }
            lca = Ancestor(root->right,n1,n2);
            return lca;
        }
    }
    else
    {
        return NULL;
    }
}
int main()
{
    struct node* root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->right=createnode(4);
    root->left->left=createnode(5);
    root->right->right=createnode(6);
    root->right->left=createnode(7);
    root->right->right->left=createnode(8);
    //root->right->right->left->left=createnode(10);
    root->right->right->right=createnode(10);
    struct node* n1 = root->right->right->right;
    struct node* n2 = root->left->left;
    struct node* lca=Ancestor(root,n1,n2);
    if(lca)
    {
 cout<<lca->data<<endl;
    }
}
Output:
1

Trie Data Structure

A trie (or a prefix tree) is a data structure similar to n-ary trees, where each node can have n children. Each child holds a reference to the next n children.

Here an example trie is discussed where some words are stored in the trie.

The TrieNode consists of the following elements:

class TrieNode {
    boolean isWord = false;
    TrieNode[] children = new TrieNode[26];
}

Here each node can have 26 children. Some children may point to null and others may point to the next character in the word.

For example, when the words "home" and "hot" are added to the trie, the state of the trie can be described as follows:
1. The first level will hold 26 children with only the 8th ("h") child holding a non-null reference. Rest of the 25 children will be null.
2. The second level which is the children of "h" will hold 25 null children with only the 15th ("o") child holding a non-null reference.
3. The third level will which is the children of "o" will hold 2 non-null references ("m" and "t") and rest 24 children will be null.
4. The fourth level will have one non-null reference ("e"), which is one of the children of "m", and "t" will hold 26 null references.

Java Code:

package com.sourabh.third;

import java.util.LinkedList;
import java.util.Queue;

class TrieNode {
 boolean isWord = false;
 TrieNode[] children = new TrieNode[26];
 public TrieNode() {
  
 }
 
 public TrieNode(String key) {
  this.add(key);
 }
 
 public boolean contains(String in) {
  TrieNode node = this;
  for(int i=0; i<in.length();i++) {
   TrieNode child = node.children[getAscii(in.charAt(i))];
   if(child == null) {
    // This particular character is not present in the current branch.
    return false;
   }
   else {
    if(in.length() - 1 == i) {
     // We have reached the end of the input string.
     return true;
    }
    else {
     node = child;
    }
   }
  }
  return false;
 }
 
 public void add(String in) {
  if(in.length() == 0) {
   this.isWord = true;
   return;
  }
  else {
   char first = in.charAt(0);
   TrieNode child = children[getAscii(first)];
   if(child == null) {
    child = new TrieNode();
    children[getAscii(first)] = child;
   }
   child.add(in.substring(1));
  }
 }
 
 public int getAscii(char c) {
  char A[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
  int i=0;
  for(i=0;i<A.length;i++) {
   if(A[i] == c) {
    break;
   }
  }
  return i;
 }
}

public class TriePrograms {
 public TrieNode createNode(String word) {
  if(word == null) {
   return new TrieNode();
  }
  else {
   return new TrieNode(word);
  }
 }
 
 public void levelOrderTraversal(TrieNode node) {
  Queue<TrieNode[]> queue = new LinkedList<>();
  if(node == null) {
   return;
  }
  queue.add(node.children);
  int thisLevel = 1;
  int nextLevel = 0;
  while(!queue.isEmpty()) {
   for(int ele = 0; ele < thisLevel; ele++) {
    TrieNode[] childrenAtThisLevel = queue.remove();
    for(int i=0; i<childrenAtThisLevel.length; i++) {
     if(childrenAtThisLevel[i] != null) {
      System.out.print(getChar(i) + ".");
      queue.add(childrenAtThisLevel[i].children);
      nextLevel++;
     }
     else {
      System.out.print(".");
     }
    }
   }
   thisLevel = nextLevel;
   System.out.println();
   for(int i=0;i<26;i++) {
    System.out.print("-");
   }
   System.out.println();
   for(int i=0;i<26;i++) {
    System.out.print("|");
   }
   System.out.println();
   nextLevel = 0;
  }
  thisLevel = nextLevel;
 }
 
 public char getChar(int ascii) {
  char A[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
  return A[ascii];
 }
}

Unit Tests:

package com.sourabh.third;

import org.junit.Assert;
import org.junit.Test;

public class TrieProgramTests {

 TriePrograms instance = new TriePrograms();
 
 @Test
 public void testContains() {
  TrieNode node = instance.createNode(null);
  node.add("home");
  Assert.assertTrue(node.contains("home"));
  node.add("house");
  Assert.assertTrue(node.contains("house"));
  node.add("hot");
  Assert.assertTrue(node.contains("hot"));
  Assert.assertFalse(node.contains("hole"));
 }
 
 @Test
 public void testConstructor() {
  TrieNode node = instance.createNode("home");
  Assert.assertTrue(node.contains("home"));
  node.add("house");
  Assert.assertTrue(node.contains("house"));
  node.add("hot");
  Assert.assertTrue(node.contains("hot"));
  Assert.assertFalse(node.contains("hole"));
 }
 
 @Test
 public void testLevelOrderTraversal() {
  TrieNode node = instance.createNode("home");
  node.add("house");
  node.add("hot");
  instance.levelOrderTraversal(node);
 }
}

Trie printed in level order:

.......h...................
--------------------------
||||||||||||||||||||||||||
..............o............
--------------------------
||||||||||||||||||||||||||
............m.......t.u......
--------------------------
||||||||||||||||||||||||||
....e..................................................................s........
--------------------------
||||||||||||||||||||||||||
..............................e......................
--------------------------
||||||||||||||||||||||||||
..........................
--------------------------
||||||||||||||||||||||||||

Given two nodes of a Binary Tree, write a program to determine the shortest distance between the two nodes.

Approach:
1. Find the lowest common ancestor of the given nodes.
2. Find the distance (levels) between the lowest common ancestor and each given node separately.
3. Add the distances obtained in Step-2.

#include<iostream>
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 return new_node;
};
int help_anc(struct node* root,node* n1,node* n2)
{
    if(root)
    {
        if(root==n1)
        {
            return 1;
        }
        else if(root==n2)
        {
            return 1;
        }
        else
        {
            return help_anc(root->left,n1,n2)+help_anc(root->right,n1,n2);
        }
    }
    else
    {
        return 0;
    }
}
struct node* Ancestor(node* root,node* n1,node* n2)
{
    if(root)
    {
        int lf = help_anc(root->left,n1,n2);
        int rf = help_anc(root->right,n1,n2);
        if(lf==1 && rf==1)
        {
            return root;
        }
        else
        {
            node* lca = Ancestor(root->left,n1,n2);
            if(lca!=NULL)
            {
                return lca;
            }
            lca = Ancestor(root->right,n1,n2);
            return lca;
        }
    }
    else
    {
        return NULL;
    }
}

int customheight(node *root,node *n1,bool *found)
{
    int lheight=0,rheight=0;
    if(root)
    {
        if(*found==false && root==n1)
        {
            *found=true;
            return 0;
        }
        else if(*found==false)
        {
            lheight=customheight(root->left,n1,found);
            rheight=0;
            if(*found==false)
            {
                rheight=customheight(root->right,n1,found);
            }
            if(*found==true)
            {
                return lheight>rheight?1+lheight:1+rheight;
            }
            else
            {
                return 0;
            }
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return 0;
    }
}
int distancethroughlca(node* n1,node* n2,node* lca)
{
    if(lca)
    {
        bool found=false;
        int dist1=customheight(lca,n1,&found);
        cout<<"Distance of "<<n1->data<<": "<<dist1<<endl;
        found=false;
        int dist2=customheight(lca,n2,&found);
        cout<<"Distance of "<<n2->data<<": "<<dist2<<endl;
        return dist1+dist2;
    }
    else
    {
        return 0;
    }
}

int main()
{
    struct node* root=createnode(1);
 root->left=createnode(2);
 root->right=createnode(3);
 root->left->right=createnode(4);
 root->left->left=createnode(5);
 root->right->right=createnode(6);
 root->right->left=createnode(7);
 root->right->right->left=createnode(8);
 //root->right->right->left->left=createnode(10);
 root->right->right->right=createnode(10);
 struct node* n1 = root->right->right->left;
 struct node* n2 = root->right->right->right;
 struct node* lca=Ancestor(root,n1,n2);
 if(lca)
 {
     cout<<"Least Common Ancestor: "<<lca->data<<endl;
 }
 cout<<"Total distance through LCA: "<<distancethroughlca(n1,n2,lca)<<endl;
}
Output:
Least Common Ancestor: 1
Distance of 8: 3
Distance of 4: 2
Total distance through LCA: 5