• RSS
  • Facebook
  • Twitter

Knowledge is Power.

  • Who you are ?

    Working on machines without understanding them ? Then you should be here..

  • Where you are ?

    Geographical location should not become a barrier to Share our knowledge.

  • What do you do ?

    Puzzles and Interview question are intended to be discussed here.

    Wednesday, June 30, 2010

    Find vertical sum of given binary tree.

    Example:

    Code:
         1
    / \
    2 3
    / \ / \
    4 5 6 7

    The tree has 5 vertical lines
    Vertical-1: nodes-4 => vertical sum is 4
    Vertical-2: nodes-2 => vertical sum is 2
    Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
    Vertical-4: nodes-3 => vertical sum is 3
    Vertical-5: nodes-7 => vertical sum is 7
    We need to output: 4 2 12 3 7

    We can do an inorder traversal and hash the column. We call Traverse(root, 0) which means the root is at column 0. As we are doing our traversal, we can hash the column and increase its value by T.data. A rough sketch of my function looks like this -

    Traverse(Tree T, int column)
    {
    if(T==NULL) return;
    Traverse(T.left, column-1);
    Hash(column) += T.data;
    Traverse(T.right, column+1);
    }

    Traverse(root, 0);
    Print Hash

    0 comments:

    Post a Comment