Print boundary or edge node of tree in anti-clockwise order

This question was asked in amazon interview. we all know that, binary tree is applicable only for numeric values, and each node has left and right node as child node and last node in tree is called leaf node(node doesn't have left and child node). 


Lets look at the below binary tree

Solution:-

Traverse and print all the left-boundary from root node in top-down direction(22,16,8), then leaf node of all the left-sub tree from left to right direction(6,10,21), then left node of the all the right-sub tree from left to right direction(23,31,33) and finally print right boundary from bottom to top direction(32,24). If you see the printed node, it doesn't print the node 20, because it's not a boundary node).

The above solution will break into 4 steps.

1. Traverse and print all the left-boundary(except leaf node 6) from root node in top-down direction(22,16,8).
2. Print leaf node of all left-sub tree from left to right direction (6,10,21).
3. Print lead node of all right-sub tree form left to right direction(23,31,33).
4. Finally print all right boundary from bottom to top direction(32,24).

Code:-

class Node 

{

    int data;

    Node left, right;

  

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTreeBoundary 

{

    Node root;

  

    // function to print leaf node of a binary tree

    void printLeaf(Node node) 

    {

        if (node != null) 

        {

        printLeaf(node.left);

  

            // Print if it is a leaf node

            if (node.left == null && node.right == null)

                System.out.print(node.data + " ");

            printLeaf(node.right);

        }

    }

  

    // Print all left boundry nodes, except a leaf node in TOP DOWN manner

    void printLeftBoundary(Node node) 

    {

        if (node != null) 

        {

            if (node.left != null) 

            {

                  

                // to ensure top down order, print the node before calling itself 

                System.out.print(node.data + " ");

                printLeftBoundary(node.left);

            } 

            else if (node.right != null) 

            {

                System.out.print(node.data + " ");

                printLeftBoundary(node.right);

            }

        }

    }

  

    // Print all right boundry nodes, except a leaf node in BOTTOM UP manner

    void printBoundaryRight(Node node) 

    {

        if (node != null) 

        {

            if (node.right != null) 

            {

                // to ensure bottom up order, print the node before calling itself 

                printBoundaryRight(node.right);

                System.out.print(node.data + " ");

            } 

            else if (node.left != null) 

            {

                printBoundaryRight(node.left);

                System.out.print(node.data + " ");

            }

        }

    }

  

    // Function to do boundary traversal in anti-clock wise direction

    void printBoundary(Node node) 

    {

        if (node != null) 

        {

            System.out.print(node.data + " ");

  

            // Step 1:- Print the left boundary in top-down manner.

            printLeftBoundary(node.left);

  

            // Step 2:- Print all leaf nodes of left-subtree from left-right direction

            printLeaf(node.left);

            // Step 3:- Print all leaf nodes of right-subtree from left-right direction            

            printLeaf(node.right);

  

            // Step 4:- Print the right boundary in bottom-up manner

            printBoundaryRight(node.right);

        }

    }

       

    public static void main(String args[]) 

    {

        BinaryTreeBoundary tree = new BinaryTreeBoundary();

        tree.root = new Node(22);

        tree.root.left = new Node(16);

        tree.root.left.left = new Node(8);

        tree.root.left.left.left = new Node(6);

        tree.root.left.left.right = new Node(10);

        tree.root.left.right = new Node(20);

        tree.root.left.right.right = new Node(21);

        

        tree.root.right = new Node(24);

        tree.root.right.left = new Node(23);

        tree.root.right.right = new Node(32);

        tree.root.right.right.left = new Node(31);

        tree.root.right.right.right = new Node(33);

        tree.printBoundary(tree.root);

  

    }

}

output:-

22 16 8 6 10 21 23 31 33 32 24 

Time Complexity: O(n). Traversing all the elements in array

Click to Read more Data structure questions and answer

If you like the above solution . Please share this blog