Amazon | Onsite | Count the number of unique vertical lines in a binary tree
Anonymous User
3157

You are given a binary tree, where each node holds a char. The left and right nodes are at a 45 degree angle from the parent node. See figure below

image

As a result, you notice that a vertical line can be drawn down A which intersect with both D and E. You can draw a second vertical line down C, which intersects with no other nodes. Finally you can draw a third vertical line down B, which intersects with not other nodes. Count the number of unique vertical lines that can be drawn such that each node has a line drawn over it. For the example above, the result is 3. Line 1 goes thru B, line 2 goes thru A, D, E and finally line 3 only goes thru C. You cannot mutate the tree's structure or modify values in any way.

Comments (6)