Example:
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