Faland 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 \ 7Expected: 4-2-1-3-7 ? In fact - 4-2-1-3.
1 / \ 2 3 / \ 4 5 / 6 / 7 / 8Expected: 8-4-2-1-3 ? In fact - 4-2-1-3, again.
alex_mistery It is just your visual perseption of the tree! The truth is that mathematically it looks like this:
______1 ______ / \ 2 3 / \ 4 5 \ 6 \ 7 \ 8
gauthamk when top view of the tree is asked, which one is meant among the two?
aminoacid Just as @AlexMistery explained
phattantran123 but if this case1 , the top view not see
trideceth12 "truth". If that's a mathematical truth show your proof.
jvedang If you add underscores to root, why not to all elements?
______1______ | | ______2______ 3 | | 4 5______ | 6______ | 7Isn't the my shown diagram show uniformness according to your design? You just broadened the root, if you broaden the root, you will also have to broaden others equally. So its answer will be 4,2,1,3,7
Reference: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
Mayur_Detroja if you only have same space everywhere how can you add left child of 3, so really parents have twice width of branch then children so all the nodes can be set.
harish_raghav333 i have the same question .This case will definitely leads to failure of our logic
Lockwood_Tommy He was simply making a point relative to mathematics. The exercise here seems to have more of a graphical significance rather than a mathematical one.
marcotuliorr I think Faland is right. This link correctly defines tree top view: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
Gprinziv Think of it this way, @marcotuliorr. Imagine if that '3' node had three consecutive children "7 - 8 - 9" (each node is the left child of its parent.) Would that branch cross over the long "4 - 5 - 6" branch and make the top-down view of the tree "9 - 2 - 1 - 3 - 6"? Of course not!
Every node's child must retain the positional properties of its parent, I.E. if 2 is to the left of 1, then 4 and 5 must also be to the left of 1. If 5 is to the left of 1, 6 must be to the left of 1 as well, etc. There's no way a branch not on the leftmost or rightmost path could be visible from the top down.
trideceth12 That makes sense. "For all nodes, everything down the right branch is to the node's right; Everything down the left branch is to the node's left."
It makes sense if you think of it in the context of a binary search tree, and left and right as less than and greater than.
jason_goemaat1 I think that link is wrong. In a binary tree, once you go left, all descendants of that child are by definition left of that parent. To get an accurate spatial representation you have to expand your tree so that the bottom level will fit if it is full. They say:
1 / \ 2 3 \ 4 \ 5 \ 6 Top view of the above binary tree is 2 1 3 6
But all nodes 'left' of the 1 should be drawn to the left of the 1. If the tree's bottom level was full it would have 16 nodes and it should be drawn that way. If you add a node '7' left of '3' using this representation, it would overlap with the '4'.
Yongping YES, I'm also confused: what's top view......
mithratalluri 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:
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! :)
avramsmart Yep this is true, we now have to worry about all nodes, not just one on the sides. Also you have to sort them by levels. This is my solution in Python.
def topView(root): uniq_lvls = [] q = Queue() q.put((root, 0)) while not q.empty(): temp = q.get() if temp[1] not in (i[1] for i in uniq_lvls): uniq_lvls.append(temp) if temp[0].left: q.put((temp[0].left, temp[1]-1)) if temp[0].right: q.put((temp[0].right, temp[1]+1)) for x in sorted(uniq_lvls, key=lambda e: e[1]): print(x[0].info, end=' ')
I am open to your suggestions of how I can improve speed and particularly memory consumption.
gelmilorenzo Hi, this seemed quite faster in a couple benchmark I ran. The main difference is the usage of dictionaries (that probably can check for items faster than in your code, to check for existence) and the queue removal. Also, the "node, score" assignation avoid some indexing I believe...
def topView(root): # Initialize the level this_level = [(root, 0)] scores = {} while this_level: # Basically iterate over the nodes on a single level for _ in range(len(this_level)): node, score = this_level.pop(0) # Skip empty nodes if not node: continue # Store the score if it's a new one! if score not in scores: scores[score] = node.info # Add the node children to the next level this_level.extend( [(node.left, score - 1), (node.right, score + 1)]) # Sort the scores and print their values # (By default the sort is on the tuple first element: the score) for _, value in sorted(list(scores.items())): print(value, end=' ')
Good coding.
renato314159 Trying to decipher some of your logic (thanks for the comments, they're a huge help).
what is happening in this line?
for _ in range(len(this_level)): node, score = this_level.pop(0)Thanks
naman1999agrawal very helpful :)
sagargupta007 Nice one..!
yudhaaditamaput1 Hi, Would you mind to explain your code? I am confused what is the purpose of using 2 different data structure LinkedList and TreeMap?and why it should remove the queueNode r but you still use the r.level and r.node.data?
xdavidliu 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 << ' '; } }
tech_boy Looks like you made it through, from the previous comments heard that even editorial solutions isn't passing the test cases #strange.
logbob0401 [deleted]
venom1724 Under 10 lines of code C++ solution
Actually there's no need to keep track of depth or to use another function, here's an example solution:
void topView(Node * root) { queue<pair<int,Node*>> q; q.push(make_pair(0,root)); map<int,Node*> ans; for(auto i=q.front();!q.empty();q.pop(),i=q.front()){ if(!i.second) continue; ans.insert(i); q.push(make_pair(i.first+1,i.second->right)); q.push(make_pair(i.first-1,i.second->left)); } for(auto i:ans) cout<<i.second->data<<" "; }
dcodeforyou [deleted]
himittal09 This is the most brilliant solution of this problem.
MADADKAROKOI Dude you are Genius!!! I struggle to hybrid different Data Structures to come up with such clever solutions, hopefully i could reach that level someday.
sadesh 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); } } }naveen_n Will this solution work for the below input?
3 / \ 5 2 / \ / \ 1 46 7 \ 9 / 10 / 11I guess "11" will not be printed in spite of it being visible, as the branch containing 9 will not be traversed?
Gprinziv The 9, 10, and 11 nodes are all to the right of the 1 node. If the 1 node had a left child, 12, it's right child would be 13, not 10. You have to expand the tree horizontally for each additional level the tree.
sasi Your example is not a binary tree. void top_view_dir(node *root, int dir) { if(root != NULL) { if(dir) { top_view_dir(root->left, 1); printf("%d ", root->data); } else { printf("%d ", root->data); top_view_dir(root->right, 0); } } } void top_view(node * root) { if(root == NULL) { return; } else { top_view_dir(root->left, 1); printf("%d ", root->data); top_view_dir(root->right, 0); } }
miron88 Exactly. I am looking for a perfect soluction for this problem.
etayluz C solution using recursion without any additional functions with time complexity of O(N) and 0 space complexity. It's the shortest solution on this forum, but it does alter the tree.
void top_view(node * root) { if (root->left) { root->left->right = NULL; top_view(root->left); } printf("%d ", root->data); if (root->right) { root->right->left = NULL; top_view(root->right); } }
sanek23994 Provided solution doesn't work if we don't want to modify our tree, right? IMHO usually if want to print some elements in some container it is always better not to modify this container...
joethomas89 Hope this helps, used a static count variable
void top_view(node * root) {
static int count=0; if (root->left && count>=0) { count++; top_view(root->left); } printf("%d ", root->data); count--; if (root->right && count<0) { count--; top_view(root->right); }}
vishal_sati Awesome!!!
prendergast And it produces memory leaks!
ace_dexter To clear memory leaks, you need to traverse once again and keep freeing memory before going to the next node. You can try in your machine with extra function for clearing them.
dennysregalado We can merge these two functions in one using default value for the second argument and define 3 possible values for each funcion call: { 0: original, 1: left , 2: right}.
void top_view(node * root, int src=0) { i f(root == NULL) return; if(src==0){ top_view(root->left, 1); printf("%d ",root->data); top_view(root->right,2); } if(src==1){ top_view(root->left, 1); printf("%d ",root->data); } if(src==2){ printf("%d ",root->data); top_view(root->right,2); } }
evanadams28 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); }
carlos_rosario11 [deleted]jittenddra perfect adams very good solution
Ridhuvarshan I don't get it. I did the same logic and got the same output except for the fact that they were not in order. How on earth does 'top view' seem to give any idea in the direction to look first. Anyway I am using your logic(same as mine with different order) guilt free as ambiguity in problem statement is not my fault. Thanks
_yash_agarwal_ Maybe, you called rightview recursively before printing data
Sort 707 Discussions, By:
Please Login in order to post a comment