We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Data Structures
  3. Trees
  4. Tree : Top View
  5. Discussions

Tree : Top View

Sort 799 Discussions, By:

  • Faland
     + 37 comments

    Maybe it needs to add detail about tree representation, i.e. that at any level left subtree never can overlap right subtree and vice versa. In the beginning I was confused - what is expected in following cases:

          1
     / \
    2   3
   / \
  4   5
       \
        6
         \
          7

    Expected: 4-2-1-3-7 ? In fact - 4-2-1-3.

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

    Expected: 8-4-2-1-3 ? In fact - 4-2-1-3, again.

  • mithratalluri
     + 14 comments

    Solution Explained (With code)

    Note: testcases have been changed for this problem. Hence, the prev. approach shown in popular comments doesn't work.

    I'm implementing the tree node with an extra variable called 'node level'. An example of the new tree looks like this:

    Vertical-_Order-_Sum-_Implementation.png

    Here's my code with suitable comments in Java

       //new class to store level of each node along with the node 
   static class QueueNode{
        Node node;
        int level;
        public QueueNode(Node node, int level){
            this.node = node;
            this.level = level;
        }
    }


    public static void topView(Node root) {
        //took a queue - similar to BFS approach
        Queue<QueueNode> queue = new LinkedList<QueueNode>();
       
        //Taking a TreeMap<first, second>
        //first - stores the level of the node
        //second - stores the node.data
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
	//why TreeMap? Because I want the nodes to be sorted from leftmost to rightmost
        
        //start (since root, level = 0)
        queue.add(new QueueNode(root, 0));
        
        while(!queue.isEmpty()){
            //remove element from queue
            QueueNode r = queue.poll();
            //if the level of this node has never been reached before -> visible in top view
            if(!map.containsKey(r.level)){
                map.put(r.level, r.node.data);
            }
            
            //add node's descendants
            //all left child node levels = node.level - 1
            //all right child node levels = node.level + 1
            if(r.node.left != null){
                queue.add(new QueueNode(r.node.left, r.level - 1));
            }
            if(r.node.right != null){
                queue.add(new QueueNode(r.node.right, r.level + 1));
            }
        }
        //since already sorted (cuz TreeMap), print from left to right
        for (Integer value : map.values()) {
            System.out.print(value + " ");
        }
    }

    I've written a blog post about this problem here: Trees: Top View of a Tree

    Please upvote this comment if helpful. Thanks! :)

  • xdavidliu
     + 3 comments

    Hackers beware! It appears that there was a major change in this problem (in the underlying test cases and checking, but sadly the problem description is highly ambiguous!) and it is no longer sufficient to print the left and right spines. This also invalidates most of the most upvoted comments and answers in this thread from 2-3 years ago. In my opinion, this problem should be labelled Medium or Hard, not Easy!

    To pass all test cases, you must keep track of the locations of every note in the entire tree, assuming all edges are of the same length and same angle. Hence, nodes may show up in the top view even if they are not in a spine!

    Here's a C++ solution that passes all test cases as of July 2018:

      using TopTable=map<int, pair<unsigned,int>>;
  void compute_table_entries(Node *nd, int xpos, unsigned depth, TopTable &tab){
    if(nd){
      auto it=tab.find(xpos);
      if(it!=tab.cend() && depth < it->second.first){
	  it->second = {depth,nd->data};
	}else{ tab.insert({xpos, {depth, nd->data}}); }
      compute_table_entries(nd->left, xpos-1, depth+1, tab);
      compute_table_entries(nd->right, xpos+1, depth+1, tab);
    }
  }
  void topView(Node * root) {
    TopTable tab;
    compute_table_entries(root,0,0,tab);
    for(auto entry: tab){
      cout << entry.second.second << ' ';
    }
  }

  • sadesh
     + 10 comments
    void top_view(Node root)
{

    if(root != null) {

        top_view(root.left, true);

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

        top_view(root.right, false);

    }

}

void top_view(Node node, boolean goLeft) {

    if(node != null) {
        if(goLeft) {
            top_view(node.left, goLeft);
            System.out.print(node.data + " ");
        } else {
            System.out.print(node.data + " ");
            top_view(node.right, goLeft);
        }
    } 

}

  • evanadams28
     + 14 comments

    My recursive solution. Like you're standing on the spine of a house roof. Look left, look down, look right. 

    void top_view(Node root)
{
    left_view(root.left);
    System.out.print(root.data + " ");
    right_view(root.right);
}

void left_view(Node root) {
    if (root == null) return;
    left_view(root.left);
    System.out.print(root.data + " ");
}

void right_view(Node root) {
    if (root == null) return;
    System.out.print(root.data + " ");
    right_view(root.right);
}
Load more conversations