Print a two-dimensional view of a Binary Tree

Posted in

Print a two-dimensional view of a Binary Tree
vinaykhatri

Vinay Khatri
Last updated on December 26, 2024

    Problem

    Given a binary tree, the task is to print the two-dimensional view of it.

    Sample Input

                 1
                /  \
               9    3 
              / \   / \
             2   5  6  10 

    Sample Output:

                        10
              3
                        6
    1
                        5
              9
    
                        2

    Approach

    This problem is based on the observations that we can make from the examples. Below are the observations:

    1) Rightmost node of the tree is printed in the first line, and the leftmost node is printed in the last line.

    2) Space count increases by a fixed quantity at every level. We need to do a reverse in-order traversal and print tree nodes. We increase space by a fixed amount at every level. The reverse in order will first explore the right subtree, then the root, and then the left subtree.

    Complexity Analysis

    The time complexity would be O(N), and the space complexity would also be O(N) due to the call stack.

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    
    struct TreeNode
    {
        int val;
        TreeNode *left, *right;
    
        TreeNode(int val)
        {
            this->val = val;
            this->left = this->right = nullptr;
        }
    };
    
    void inOrder(TreeNode* root, int gap = 0, int height = 10)
    {
        // Base case
        if (!root) {
            return;
        }
    
        // increase the gap count
        gap += height;
    
        // print right child
        inOrder(root->right, gap);
        cout << endl;
    
        // print the current node after gap
        for (int i = height; i < gap; i++) {
            cout << ' ';
        }
    
        cout << root->val;
    
        // print left child
        cout << endl;
        inOrder(root->left, gap);
    }
    
    int main()
    {
        TreeNode* root = new TreeNode(1);
        root->left = new TreeNode(9);
        root->right = new TreeNode(3);
        root->left->left = new TreeNode(2);
        root->left->right = new TreeNode(5);
        root->right->left = new TreeNode(6);
        root->right->right = new TreeNode(10);
    
        inOrder(root);
    
        return 0;
    }

    Output

                        10
              3
                        6
    1
                        5
              9
                        2
    

    Java Programming

    class TreeNode
    {
        int val;
        TreeNode left, right;
    
        TreeNode(int val)
        {
            this.val = val;
            this.left = this.right = null;
        }
    }
    
    class Main
    {
        public static void inOrder(TreeNode root, int gap, int height)
        {
            // Base case
            if (root == null) {
                return;
            }
    
            // increase the gap
            gap += height;
    
            // print right child
            inOrder(root.right, gap, height);
            System.out.println();
    
            // print the current node after spaces
            for (int i = height; i < gap; i++) {
                System.out.print(' ');
            }
    
            System.out.print(root.val);
    
            // print left child
            System.out.println();
            inOrder(root.left, gap, height);
        }
    
        public static void main(String[] args)
        {
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(9);
            root.right = new TreeNode(3);
            root.left.left = new TreeNode(2);
            root.left.right = new TreeNode(5);
            root.right.left = new TreeNode(6);
            root.right.right = new TreeNode(10);
    
            int gap = 0, height = 10;
            inOrder(root, gap, height);
        }
    }

    Output

                        10
              3
                        6
    1
                        5
              9
                        2
    

    Python Programming

    class TreeNode:
        def __init__(self, val, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
    
    def inOrder(root, gap, height):
        # Base case
        if root is None:
            return
    
        # increase the gap
        gap += height
    
        # print right child
        inOrder(root.right, gap, height)
        print()
    
        # print the current node
        for i in range(height, gap):
            print(' ', end='')
    
        print(root.val, end='')
    
        # print left child
        print()
        inOrder(root.left, gap, height)
    
    root = TreeNode(1)
    root.left = TreeNode(9)
    root.right = TreeNode(3)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(10)
    
    gap = 0
    height = 10
    inOrder(root, gap, height)

    Output

                      10
              3
                        6
    1
                        5
              9
                        2

    People are also reading:

    Leave a Comment on this Post

    0 Comments