CareerCup

This question is completely different than tree walk algorithm.
There are two different solutions to this problem. Running time of them is O(n lg n) and O(n).
Solution 1 ( O(n lg n) ):
Set a key value to each node. Set the key of root to n. Start BFS from the root. At each step when you visit a node, set the left child key to nodes’ key minus one and the right child key to nodes’ key plus one; then insert the node at the end of an array. After BFS is finished, sort the array based on the key using a stable sorting algorithm in O(n lg n).
Solution 2 ( O(n) ):
Create an array of size 2n. Simulate the counting sort during BFS, such that after your BFS each index includes the count of nodes with that key. Repeat BFS one more time; insert the elements in the sorted format in the second array of size n by using the information of the first array in a counting sort manner. This takes O(n) to finish.

Note: Both algorithms need O(n) space.

I would first define what a column in a tree is. I think a recursion can help:
#columns(root)=#columns(root.left)+length(root.value)+#columns(root.right),
#columns(empty tree)=0

The position at which to print node value is: (level of the node, #columns(root.left))

If I can't print at x,y positions I need a level order traversal to print line by line.

It is O(n) time and O(n) space (for the level order traversal and the position)

Note, there are better ways to layout the tree, if the tree has branches that can be kind of nested into each other.

I think he/she means the columns in this format.

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

That would be 1, 8, 5, 7, 3, 2, 9, 4, 6.
Those solutions are correct in my opinion. I think finding better than O(n) is not possible? Any suggestions?

If you really think about it, this question doesn't make any sense. the question is assuming an invalid graphical layout of a binary tree. Layout a large binary tree on paper and you will see what I mean. I am surprised that facebook would even ask such a faulty question.

# Time:  O(n)
# Space: O(n)

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

import collections
# BFS + hash solution.
class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        cols = collections.defaultdict(list)
        queue = [(root, 0)]
        for node, i in queue:
            if node:
                cols[i].append(node.val)
                queue += (node.left, i - 1), (node.right, i + 1)
        return [cols[i] for i in xrange(min(cols.keys()), max(cols.keys()) + 1)] \
            if cols else []

if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(4)
    result = Solution().verticalOrder(root)
    print result

##Output : [[2], [1, 5, 6], [3], [4]]