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.
This question is so terribly defined it makes me wanna p*** in the cereal of whoever made this question. What defines a view of a tree as being top down? Well in the problem description its defined in one single example EXCEPT THE F****** EXAMPLE DOESN'T COVER 80% OF HOW THE VIEW IS DEFINED.
Assuming all branches are evenly spaced: i.e. a left branch is 1 unit down and 1 unit to the left of its parent, the highest branch to be left or right of the root and all of its proceeding children will be what you could see. For example, if the root node has a left child, the left child and all of its left children are what you can see. The highest/first child to be right of the root and all of its right sided children would be visible as well.
If you had:
1
\
15
/
3
/ \
2 4
Then you could see 15 and all of its proceeding right children, you could also see two since its left of 1 and all of its left children. Since all diagnal lines you could form all have a slope of 1 or -1, you could never have a situation where you could see one of four's imaginarily infine right sided children because 15 set the line of sight at a higher point. Same logic follows that four's imaginarily infine left sided children could never enter the line of sight of root because 2 already determined roots left sided line of sight.
I made one other assumption that branches / connections between branches were opaque. I wrote code based on these priciples. F*** this problem.
`def topView(root, direction="Root"):
leftNode = None
rightNode = None
values = []
queue = Queue()
queue.enqueue((root, 0))
while queue.isEmpty() is False and (leftNode is None or rightNode is None):
node = queue.dequeue()
#print(f"node observered: {node[0].info}, it's x: {node[1]}")
if node[1] > 0 and rightNode is None:
rightNode = node[0]
#print(f"right node assgned: {rightNode.info}")
if node[1] < 0 and leftNode is None:
leftNode = node[0]
#print(f"left node assgned: {leftNode.info}")
if node[0].left is not None:
#print(f"left: {node[0].left.info}")
queue.enqueue((node[0].left, node[1] - 1))
if node[0].right is not None:
#print(f"right: {node[0].right.info}")
queue.enqueue((node[0].right, node[1] + 1))
while leftNode is not None:
print(f" lefts value: {leftNode.info}")
values.append(str(leftNode.info))
leftNode = leftNode.left
values = list(reversed(values))
values.append(str(root.info))
while rightNode is not None:
print(f" rights value: {rightNode.info}")
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tree : Top View
You are viewing a single comment's thread. Return to all comments →
This question is so terribly defined it makes me wanna p*** in the cereal of whoever made this question. What defines a view of a tree as being top down? Well in the problem description its defined in one single example EXCEPT THE F****** EXAMPLE DOESN'T COVER 80% OF HOW THE VIEW IS DEFINED.
Assuming all branches are evenly spaced: i.e. a left branch is 1 unit down and 1 unit to the left of its parent, the highest branch to be left or right of the root and all of its proceeding children will be what you could see. For example, if the root node has a left child, the left child and all of its left children are what you can see. The highest/first child to be right of the root and all of its right sided children would be visible as well.
If you had: 1 \ 15 / 3 / \ 2 4 Then you could see 15 and all of its proceeding right children, you could also see two since its left of 1 and all of its left children. Since all diagnal lines you could form all have a slope of 1 or -1, you could never have a situation where you could see one of four's imaginarily infine right sided children because 15 set the line of sight at a higher point. Same logic follows that four's imaginarily infine left sided children could never enter the line of sight of root because 2 already determined roots left sided line of sight.
I made one other assumption that branches / connections between branches were opaque. I wrote code based on these priciples. F*** this problem.
`def topView(root, direction="Root"):