Maximum projection on x-axis of a binary tree

Question

Given a binary tree in a coordinate plane with its root having coordinates (x,y) . We need to find the maximum projection on x-axis of this tree. That is , basically we need to find the MAXIMUM width of this tree. The tree can be skew as well.

Examples :

    1
   / \
  2   3
 /   / \
4   5   6

Width = 5

    1
   / \
  2   3
 /  
4   

Width = 4

    1
   / 
  2  
 /   
4   

Width = 3

My logic was to basically find the left most node and the right most node and subtract their x-coordinates. On going from root to left subtree x becomes x-1 and y becomes y+1 and on going to right subtree x becomes x+1. Upon finding these 2 coordinates xLeft and xRight , we can find the maximum width. But I was having trouble coding it.

Can anyone tell how to go about it ? It is not a homework question , but it was a programming puzzle I read somewhere.

Answer 1

This is a level-order traversal problem. As you traverse the tree in level order, track the width of the largest level. When you are done, the leftmost node and the rightmost node at that level will give you the final projection you are looking for.

EDIT:

mbeckish: The above solution assumes the question was about the largest cross-section. But if that's not the case, level order still works. Except the code must track both minX and maxX during traversal. minX would track the leftmost node and maxX would track the rightmost node. Then the answer would be maxX-minX+1.

This site has a number of well-documented bst traversal code you can modify.