Current Status
Exp: 12+ Exp
Work: SDE2 at Amazon
Location: Palo Alto, CA
Interview
Uber phone screen for a position at SFO
My Thoughts:
I had attended uber phone screen, sometime on Jan first week. This below was the question asked, it was similar to
545 Boundary of Binary Tree (premium)
But the interviewer told
Don’t construct binary tree and then print the boundary of the binary tree
I didnot know the how to proceed further without constructing the binary tree.
Problem Statement
A perfect binary tree is a binary tree that satisfies two conditions:
All non-leaf nodes have exactly 2 children
All leaf nodes are at the same depth in the tree.
For example, the following is a perfect binary tree:
Your task is to write a program that reads a perfect binary tree and prints the values of all nodes on the outer “edges” of the tree in counterclockwise order, starting at the root. You should try to do this as efficiently as possible.
For example, if you were given the following tree:
Then the order of nodes printed should be:
1 7 14 23 28 5 2 9 21 18 17 6 4
The output should begin with the root node and should finish with the right child of the root node. Each node’s value should only be printed once.
Input Format
The input will be provided via stdin as a list of integer values, separated by spaces. The first integer will be the depth of the tree, and the following numbers will be the integer values to be stored in each node, specified in pre-traversal depth-first order.
For example, the binary tree above would be represented by the following input:
4 1 7 14 23 28 8 5 2 4 3 9 21 6 18 17
Output Format
Node values should be printed to stdout, with each node value on a separate line. There should be no other output.
For the example input above, the correct output would be:
1
7
14
23
28
5
2
9
21
18
17
6
4