Skip to main content
Software Engineering

Return to Answer

Fixed rookie mistake: in-order -> level-order
Source Link
user22815
user22815

Sounds like you need a type of heap with some modified properties. First, use a min-heap instead of a max-heap: every node is less than the values of its children, and add a constraint that a node is greater than its siblings to the left.

One of the neat features of a heap is that it is a balanced binary tree: the depth of all leaf nodes vary by at most 1. Furthermore, leaf nodes are populated left to right. While this is not quite the same representation as you have, it makes the whole thing a ton easier.

If you take a tree with these properties and perform an ina level-order traversal, you can easily convert it to and from an array:

root = 6 root->left = 1 root->right = 9 root->left->left = 8 root->left->right = 2

InLevel-order traversal gives the following: 6, 1, 9, 8, 2.

Note how each level takes 2^n elements in that array, where n is the depth of the nodes at that level. The root node has depth 0, so it takes 2^0 = 1 element. Next layerlevel has depth 1, so it takes 2^1 = 2 elements. This property means there is a direct correlation between a specific element in the tree and its array position.

Now perform an efficient sort on that array, and you get: 1, 2, 6, 8, 9.

Perform the reverse of the first transformation. Element 0 is the root, Elements 1 and 2 are the next layerlevel, elements 3, 4, (and 5, 6 if present) are the next layerlevel.

root = 1 root->left = 2 root->right = 6 root->left->left = 8 root->left->right = 9

If you need to maintain the fact that leaves are not populated left to right, or the tree is not balanced, you can add gaps by saying certain nodes are null and modify a sort algorithm to leave null values in-place. Not ideal, but it can allow you to leverage the properties of a heap to do this. InLevel-order sorting pretty much has to be done using a heap as far as I am aware (made it through a B.S. and M.S. in computer science without ever hearing or seeing another way to do this, and you know the real world doesn't care).

Sounds like you need a type of heap with some modified properties. First, use a min-heap instead of a max-heap: every node is less than the values of its children, and add a constraint that a node is greater than its siblings to the left.

One of the neat features of a heap is that it is a balanced binary tree: the depth of all leaf nodes vary by at most 1. Furthermore, leaf nodes are populated left to right. While this is not quite the same representation as you have, it makes the whole thing a ton easier.

If you take a tree with these properties and perform an in-order traversal, you can easily convert it to and from an array:

root = 6 root->left = 1 root->right = 9 root->left->left = 8 root->left->right = 2

In-order traversal gives the following: 6, 1, 9, 8, 2.

Note how each level takes 2^n elements in that array, where n is the depth of the nodes at that level. The root node has depth 0, so it takes 2^0 = 1 element. Next layer has depth 1, so it takes 2^1 = 2 elements. This property means there is a direct correlation between a specific element in the tree and its array position.

Now perform an efficient sort on that array, and you get: 1, 2, 6, 8, 9.

Perform the reverse of the first transformation. Element 0 is the root, Elements 1 and 2 are the next layer, elements 3, 4, (and 5, 6 if present) are the next layer.

root = 1 root->left = 2 root->right = 6 root->left->left = 8 root->left->right = 9

If you need to maintain the fact that leaves are not populated left to right, or the tree is not balanced, you can add gaps by saying certain nodes are null and modify a sort algorithm to leave null values in-place. Not ideal, but it can allow you to leverage the properties of a heap to do this. In-order sorting pretty much has to be done using a heap as far as I am aware (made it through a B.S. and M.S. in computer science without ever hearing or seeing another way to do this, and you know the real world doesn't care).

Sounds like you need a type of heap with some modified properties. First, use a min-heap instead of a max-heap: every node is less than the values of its children, and add a constraint that a node is greater than its siblings to the left.

One of the neat features of a heap is that it is a balanced binary tree: the depth of all leaf nodes vary by at most 1. Furthermore, leaf nodes are populated left to right. While this is not quite the same representation as you have, it makes the whole thing a ton easier.

If you take a tree with these properties and perform a level-order traversal, you can easily convert it to and from an array:

root = 6 root->left = 1 root->right = 9 root->left->left = 8 root->left->right = 2

Level-order traversal gives the following: 6, 1, 9, 8, 2.

Note how each level takes 2^n elements in that array, where n is the depth of the nodes at that level. The root node has depth 0, so it takes 2^0 = 1 element. Next level has depth 1, so it takes 2^1 = 2 elements. This property means there is a direct correlation between a specific element in the tree and its array position.

Now perform an efficient sort on that array, and you get: 1, 2, 6, 8, 9.

Perform the reverse of the first transformation. Element 0 is the root, Elements 1 and 2 are the next level, elements 3, 4, (and 5, 6 if present) are the next level.

root = 1 root->left = 2 root->right = 6 root->left->left = 8 root->left->right = 9

If you need to maintain the fact that leaves are not populated left to right, or the tree is not balanced, you can add gaps by saying certain nodes are null and modify a sort algorithm to leave null values in-place. Not ideal, but it can allow you to leverage the properties of a heap to do this. Level-order sorting pretty much has to be done using a heap as far as I am aware (made it through a B.S. and M.S. in computer science without ever hearing or seeing another way to do this, and you know the real world doesn't care).

Source Link
user22815
user22815

Sounds like you need a type of heap with some modified properties. First, use a min-heap instead of a max-heap: every node is less than the values of its children, and add a constraint that a node is greater than its siblings to the left.

One of the neat features of a heap is that it is a balanced binary tree: the depth of all leaf nodes vary by at most 1. Furthermore, leaf nodes are populated left to right. While this is not quite the same representation as you have, it makes the whole thing a ton easier.

If you take a tree with these properties and perform an in-order traversal, you can easily convert it to and from an array:

root = 6 root->left = 1 root->right = 9 root->left->left = 8 root->left->right = 2

In-order traversal gives the following: 6, 1, 9, 8, 2.

Note how each level takes 2^n elements in that array, where n is the depth of the nodes at that level. The root node has depth 0, so it takes 2^0 = 1 element. Next layer has depth 1, so it takes 2^1 = 2 elements. This property means there is a direct correlation between a specific element in the tree and its array position.

Now perform an efficient sort on that array, and you get: 1, 2, 6, 8, 9.

Perform the reverse of the first transformation. Element 0 is the root, Elements 1 and 2 are the next layer, elements 3, 4, (and 5, 6 if present) are the next layer.

root = 1 root->left = 2 root->right = 6 root->left->left = 8 root->left->right = 9

If you need to maintain the fact that leaves are not populated left to right, or the tree is not balanced, you can add gaps by saying certain nodes are null and modify a sort algorithm to leave null values in-place. Not ideal, but it can allow you to leverage the properties of a heap to do this. In-order sorting pretty much has to be done using a heap as far as I am aware (made it through a B.S. and M.S. in computer science without ever hearing or seeing another way to do this, and you know the real world doesn't care).