Maximum projection on the x-axis of a binary tree
Given a binary tree in the coordinate plane with its root having coordinates (x, y). We need to find the maximum projection on the x-axis of this tree. That is, basically, we need to find the MAX width of this tree. The tree can also be distorted.
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 leftmost node and the rightmost node and subtract their x coordinates. When moving from the root to the left subtree x
becomes x-1
, and y becomes, y+1
and when moving to the right subtree x
becomes x+1
. By finding these 2 coordinates xLeft and xRight, we can find the maximum width. But I had trouble coding it.
Can anyone tell me how to do this? This is not a homework question, but it was a programming puzzle I read somewhere.
source to share
This is a level traversal problem. As you traverse the tree in level order, trace the width of the largest level. When you're done, the leftmost node and the rightmost node at that level will give you the final prediction you're looking for.
EDIT:
mbeckish: The above solution assumes the question was about the largest cross section. But if it doesn't, the order of the levels still works. Also, the code has to keep track of both minX
and maxX
during the traversal. minX
will keep track of the leftmost node and maxX
will keep track of the rightmost node. Then the answer will be maxX-minX+1
.
This site contains a number of well-documented workarounds that you can change.
source to share
You can solve this by following the standard tree traversal algorithm, keeping the x coordinate of the current node. When you go left, you decrease x, and whenever you go right, you decrease x. This is shown here:
void ExtremalNodes(Node* curr, int x, int& maxX, int& minX) {
if (curr == nullptr) return;
maxX = std::max(x, maxX);
minX = std::min(x, minY);
ExtremalNodes(curr->left, x - 1, maxX, minX);
ExtremalNodes(curr->right, x + 1, maxX, minX);
}
int TreeProjection(Node* root) {
if (root == nullptr) return 0;
int maxX = 0;
int minX = 0;
ExtremalNodes(root, 0, maxX, minX);
return maxX - minX + 1;
}
Hope this helps!
source to share