To print the boundary of Binary Tree

Question

I have been asked in an interviews to print the boundary of the Binary Tree. For example.

      1
   /    \
  2      3
 /  \   /  \
4    5 6    7
    /   \     \
   8     9     10

Answer will be : 1, 2, 4, 8, 9, 10, 7, 3

I have given the following answer.

First Method :

I have used a Bool variable to solve the above problem.

void printLeftEdges(BinaryTree *p, bool print) {
   if (!p) return;
   if (print || (!p->left && !p->right))
       cout << p->data << " ";
   printLeftEdges(p->left, print);
   printLeftEdges(p->right, false);
}

void printRightEdges(BinaryTree *p, bool print) {
   if (!p) return;
   printRightEdges(p->left, false);
   printRightEdges(p->right, print);
   if (print || (!p->left && !p->right))
   cout << p->data << " ";
}

void printOuterEdges(BinaryTree *root) {
   if (!root) return;
   cout << root->data << " ";
   printLeftEdges(root->left, true);
   printRightEdges(root->right, true);
}

His Response : You have used Bool variable so many times. Can you solve this without using that.

Second Method :

I simply used tree traversal to solve this problem.

1. Print the left boundary in top-down manner.
2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts:
     2.1 Print all leaf nodes of left sub-tree from left to right.
     2.2 Print all leaf nodes of right subtree from left to right.
3. Print the right boundary in bottom-up manner.

His Response : He was not happy with this method too. He told that you are traversing the tree 3 times. That is too much. Give another solution if you have any.

Third Method : This time i have went for Level Order traversal (BFS).

 1: Print starting and ending node of each level
 2: For each other node check if its both the children are <b>NULL</b> then print that node too.

His Response : He was not seems happy with this method too because this method takes extra memory of order O(n).

My question is that Tell me a method which traverse tree single times, do not use any Bool variable and do not use any extra memory. Is it possible?

Filberte

I think O(1) times traverse is not that much bad! [second solution] – Gymnastic

@Gymnastic It was not O(1), it is O(n). Because we have to traverse all the nodes at least once. – Filberte

O(1) refer to 3. traversing 3 time or 1 times doesn't really matter , maybe except for employing – Gymnastic

Answer 1

I guess this should do the trick:

traverse(BinaryTree *root)
{
  if (!root) return;
  cout << p->data << " ";
  if (root->left ) traverseL(root->left ); //special function for outer left
  if (root->right) traverseR(root->right); //special function for outer right
}

traverseL(BinaryTree *p)
{
  cout << p->data << " ";
  if (root->left ) traverseL(root->left ); //still in outer left
  if (root->right) traverseC(root->right); 
}

traverseR(BinaryTree *p)
{
  if (root->left ) traverseC(root->left );
  if (root->right) traverseR(root->right); //still in outer right
  cout << p->data << " ";
}

traverseC(BinaryTree *p)
{
  if (!root->left && !root->right) //bottom reached
    cout << p->data << " ";
  else
  {
    if (root->left ) traverseC(root->left );
    if (root->right) traverseC(root->right);
  }
}

Start with the traverse function. Got rid of the null-queries at the beginning of each method (avoids one function call at each end). Does not need bool variables, simply uses three different traversal methods:

• one for the left edge, outputting the node before traversal
• one for the right edge, outputting the node after traversal
• one for all other nodes, outputting the node if there are no siblings.

Neocene

I do not have sufficient point to upvote a solution. Whenever i will get sufficient point i will. – Filberte

Thanks. Good luck with your interview. – Neocene

Haven't you missed the cases in traverseL where the nodes are on left boundary but are not leaf nodes. Like once root-left is null and root-right is not. Now this root-right has more nodes in root-left. These nodes will not be printed. – Stanislaw

@Stanislaw That depends a bit what the definition of the boundary is. You are right, I only consider the left-only, right-only and leaf nodes. What you mean is more like the start and end of each level as above mentioned third method. For the left edge that is possible by returning the depth of the deepest returned value so far, and continuing in the traverseL path if we are deeper than that. For the right edge, traversal in the opposite direction, and for both, additional memory would be required. So I doubt that the question went in that direction. But it is not specified, you could be right. – Neocene

Thanks for clarifying. – Stanislaw

Answer 2

Below is a recursive solution in Python3 with time complexity O(n). Algorithm here is to print left most nodes from top to bottom, leaf nodes from left to right and right most nodes from bottom to top. Adding boolean flags (isLeft,isRight) for left and right tree traversal simplifies the code and drives the time complexity of O(n).

#Print tree boundary nodes
def TreeBoundry(node,isLeft,isRight):
    #Left most node and leaf nodes
    if(isLeft or isLeaf(node)): print(node.data,end=' ')
    #Process next left node
    if(node.getLeft() is not None): TreeBoundry(node.getLeft(), True,False)
    #Process next right node
    if(node.getRight() is not None):TreeBoundry(node.getRight(), False,True)
    #Right most node
    if(isRight and not isLeft and  not isLeaf(node)):print(node.data,end=' ')

#Check is a node is leaf
def isLeaf(node):
   if (node.getLeft() is None and  node.getRight() is None):
       return True
   else:
       return False

#Get started
#https://github.com/harishvc/challenges/blob/master/binary-tree-edge-nodes.py
TreeBoundry(root,True,True)

Ichnology

I'm not sure, your solution is correct. The last line in TreeBoundary prints not only the right boundary, but also any node inside the tree, that was reached from an immediate right-turn. Instead you need to track if it was reached purely from right-turns. Besides, I don't see the necessity for the booleans, as the three states are easily tracked by the function pointer, and a lot of condition checking can be avoided. – Neocene

Answer 3

Method O(n) No extra space and single traversal of tree.

I divided the Tree Nodes into four types of nodes

Type 1 -> Nodes which form the left boundary(eg 8)

Type 0 -> Nodes which do not form the boundar(eg 12)

Type 3 -> Nodes which form the right boundary(eg 22)

Leaf Nodes(eg 4,10,14)

In my method i am just doing recurrsion method of tree traversal (just modified) where my function is of this form

  void recFunc(btNode *temp,int type)
   {
      //Leaf Nodes
     if((temp->left == NULL)&&(temp->right == NULL))
                 cout << temp->data <<  " ";
     // type -1 Nodes must be printed before their children
   else if(type == 1)cout << temp->data << " ";
   else {;}


   if(type == 3)
   {
    if(temp->left)recFunc(temp->left,0);
    if(temp->right)recFunc(temp->right,3);
     //type 3 nodes must be printed after their children
    cout << temp->data << " ";
   }   
   else if(type == 1)
   {
    if(temp->left)recFunc(temp->left,1);
    if(temp->right)recFunc(temp->right,0);
   }
   else if(type == 0)
   {
    if(temp->left)recFunc(temp->left,0);
    if(temp->right)recFunc(temp->right,0);
   }
   else {;}
    }

where i have modofied the

1. In my recurrsive function Nodes of type 1 must make their left nodes as type 1 and must be printed before calling their children(if they exist)
2. Nodes Of Type 3 must be printed in reverse order .So they must be printed after call to their children.They must also assign their right children as Type 3 Nodes
3. Nodes Of Type 0 must not be printed and they assign their children as type 0 Nodes
4. Leaf Nodes must be directly printed only and return

Link to Code

Clannish

In the tree you have given: if there is no 4, then 12 has to be printed. How this is handled in your code? – Jackleg

Answer 4

//4 diff list for 4 different part of the solution 1)left border 2)right border 3)leaf in left tree 4)leaf in right tree

public class PRintBinaryTreeBoundary {


    ArrayList<TreeNode> leftBorderList=new ArrayList<>();
    ArrayList<TreeNode> leftLEafNode=new ArrayList<>();

    ArrayList<TreeNode> rightBorderList=new ArrayList<>();
    ArrayList<TreeNode> rightLEafNode=new ArrayList<>();



    public static void main(String[] args) {
        // TODO Auto-generated method stub
         /*  1
           /    \
          2      3
         /  \   /  \
        4    5 6    7
            /   \     \
           8     9     10*/
        TreeNode one=new TreeNode(1);

        TreeNode two=new TreeNode(2);
        TreeNode three=new TreeNode(3);
        TreeNode four=new TreeNode(4);
        TreeNode five=new TreeNode(5);
        TreeNode six=new TreeNode(6);
        TreeNode seven=new TreeNode(7);
        TreeNode eight=new TreeNode(8);

        TreeNode nine=new TreeNode(9);
        TreeNode ten=new TreeNode(10);


        one.left=two; one.right=three;

        two.left=four;two.right=five;

        three.left=six;three.right=seven;


        five.left=eight;

        six.right=nine;

        seven.right=ten;


        PRintBinaryTreeBoundary p=new PRintBinaryTreeBoundary();
        p.print(one);





    }

    private void print(TreeNode one) {
        System.out.println(one.val);

        populateLeftBorderList(one.left);
        populateRightBorderList(one.right);

        populateLeafOfLeftTree(one.left);
        populateLeafOfRightTree(one.right);


        System.out.println(this.leftBorderList);
        System.out.println(this.leftLEafNode);

        System.out.println(this.rightLEafNode);
        Collections.reverse(this.rightBorderList);
        System.out.println(this.rightBorderList);



    }

    private void populateLeftBorderList(TreeNode node) {

        TreeNode n = node;

        while (n != null) {
            this.leftBorderList.add(n);
            n = n.left;
        }

    }

    private void populateRightBorderList(TreeNode node) {

        TreeNode n = node;
        while (n != null) {
            this.rightBorderList.add(n);
            n = n.right;
        }

    }

    private void populateLeafOfLeftTree(TreeNode leftnode) {

        Queue<TreeNode> q = new LinkedList<>();
        q.add(leftnode);

        while (!q.isEmpty()) {

            TreeNode n = q.remove();

            if (null == n.left && null == n.right && !this.leftBorderList.contains(n)) {
                leftLEafNode.add(n);
            }

            if (null != n.left)
                q.add(n.left);

            if (null != n.right)
                q.add(n.right);

        }
    }

    private void populateLeafOfRightTree(TreeNode rightNode) {

        Queue<TreeNode> q = new LinkedList<>();
        q.add(rightNode);

        while (!q.isEmpty()) {

            TreeNode n = q.remove();

            if (null == n.left && null == n.right && !this.rightBorderList.contains(n)) {
                rightLEafNode.add(n);
            }

            if (null != n.left)
                q.add(n.left);

            if (null != n.right)
                q.add(n.right);

        }

    }
}

Mikes

Answer 5

Hope this helps:

// Java program to print boundary traversal of binary tree 

/* A binary tree node has data, pointer to left child 
   and a pointer to right child */
class Node { 
int data; 
Node left, right; 

 Node(int item) 
 { 
    data = item; 
    left = right = null; 
 } 
} 

class BinaryTree { 
Node root; 

// A simple function to print leaf nodes of a binary tree 
void printLeaves(Node node) 
{ 
    if (node != null) { 
        printLeaves(node.left); 

        // Print it if it is a leaf node 
        if (node.left == null && node.right == null) 
            System.out.print(node.data + " "); 
        printLeaves(node.right); 
    } 
} 

// A function to print all left boundary nodes, except a leaf node. 
// Print the nodes in TOP DOWN manner 
void printBoundaryLeft(Node node) 
{ 
    if (node != null) { 
        if (node.left != null) { 

            // to ensure top down order, print the node 
            // before calling itself for left subtree 
            System.out.print(node.data + " "); 
            printBoundaryLeft(node.left); 
        } 
        else if (node.right != null) { 
            System.out.print(node.data + " "); 
            printBoundaryLeft(node.right); 
        } 

        // do nothing if it is a leaf node, this way we avoid 
        // duplicates in output 
    } 
} 

// A function to print all right boundary nodes, except a leaf node 
// Print the nodes in BOTTOM UP manner 
void printBoundaryRight(Node node) 
{ 
    if (node != null) { 
        if (node.right != null) { 
            // to ensure bottom up order, first call for right 
            // subtree, then print this node 
            printBoundaryRight(node.right); 
            System.out.print(node.data + " "); 
        } 
        else if (node.left != null) { 
            printBoundaryRight(node.left); 
            System.out.print(node.data + " "); 
        } 
        // do nothing if it is a leaf node, this way we avoid 
        // duplicates in output 
    } 
} 

// A function to do boundary traversal of a given binary tree 
void printBoundary(Node node) 
{ 
    if (node != null) { 
        System.out.print(node.data + " "); 

        // Print the left boundary in top-down manner. 
        printBoundaryLeft(node.left); 

        // Print all leaf nodes 
        printLeaves(node.left); 
        printLeaves(node.right); 

        // Print the right boundary in bottom-up manner 
        printBoundaryRight(node.right); 
    } 
} 

// Driver program to test above functions 
public static void main(String args[]) 
{ 
    BinaryTree tree = new BinaryTree(); 
    tree.root = new Node(20); 
    tree.root.left = new Node(8); 
    tree.root.left.left = new Node(4); 
    tree.root.left.right = new Node(12); 
    tree.root.left.right.left = new Node(10); 
    tree.root.left.right.right = new Node(14); 
    tree.root.right = new Node(22); 
    tree.root.right.right = new Node(25); 
    tree.printBoundary(tree.root); 
} 
} 

Boundary Traversal of binary tree

Octahedral

Answer 6

Below is a Java O(n) time complexity solution that solves the problem of counting duplicates (ex: left node that is also leaf node)

class Node {
    Node left;
    Node right;
    int data;
    Node(int d) {
       data = d;
       left = right = null;
    }
}

class BinaryTree {
    Node root;
    public void getBoundary() {
       preorderLeft(root);
       inorderLeaves(root);
       postorderRight(root);
    }
    public boolean isLeaf(Node node) {
       if (node != null && node.left == null && node.right == null) return true;
       return false;
    }
    public void preorderLeft(Node start) {
       if (start != null && isLeaf(start) == false) System.out.print(start.data + " ");
       if (start.left != null) preorderLeftSide(start.left);
    }
    public void inorderLeaves(Node start) {
       if(start == null) return;
       if(start.left != null) inorderLeaves(start.left);
       if(start.left == null && start.right == null) System.out.print(start.data + " ");
       if(start.right != null) inorderLeaves(start.right);
    }
    public void postorderRight(Node start) {
       if(start.right != null) postorderRightSide(start.right);
       if(start != null && isLeaf(start) == false) System.out.print(start.data + " ");
    }
}

This YouTube video was very helpful. The author write comments explaining each method and shows how to skip duplicates. https://youtu.be/7GzuxmZ34cI

Lenten

Answer 7

By using vertical distance from the root node and level we can solve it using list and map.

map<int,int>tmap;    #store the vertical distance and level
list<int>llist;  #store the node values

void Buildfunction(root,d, l){
    if(root == NULL){
        return; 
    } else if(tmap.count(d) == 0){
       tmap[d] = l;
       llist.push_back(root->data);
    } else if((root->left == NULL && root->right==NULL) || tmap[d] < l){
       tmap[d] = l;
       llist.push_back(root->data);  
    }
    Buildfunction(root->left,d--,l++);
    Buildfunction(root->right,d++,l++);  
}

where d pointing to vertical distance from current node respect to root and l pointing to level of the current node starting from 0

Dhiren

Answer 8

The following python solution worked for me. It handles all the cases. Based on the solution of @azt

class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def printLeaves(root):
    if (root):
        printLeaves(root.left)
        if root.left is None and root.right is None:
            print(root.data),

        printLeaves(root.right)


def printBoundaryC(node):
    if not node.left or not node.right:
        print(node.data)
    if node.left:
        printBoundaryC(node.left)
    if node.right:
        printBoundaryC(node.right)


def printBoundaryLeft(root):
    print(root.data)
    if root.left:
        printBoundaryLeft(root.left)
    if root.right:
        printBoundaryC(root.right)

def printBoundaryRight(root):
    if root.right:
        printBoundaryRight(root.right)
    elif root.left:
        printBoundaryC(root.left)
    print(root.data)

def printBoundary(root):
    if (root):
        print(root.data)

        if root.left:
            printBoundaryLeft(root.left)
        if root.right:
            printBoundaryRight(root.right)



root = Node(20)
root.left = Node(8)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.left.right = Node(5)
root.left.right.right = Node(14)
root.right = Node(22)
root.right.right = Node(25)
printBoundary(root)

Predigestion