The interviewee wrote the excellent idea to figure out the completeness of binary tree. His idea is to calculate total nodes in the binary tree first, and then assign each node with a value based on the structure of tree, the root node has value 0, and left child is parent node's value * 2 + 1, right child is parent node's value * 2 + 2. And then if it is a complete binary tree, all nodes value should be in the range of [0, totalNodes - 1]. Apply preorder travesal, and check if node's value is smaller than total nodes.
Tuesday, March 31, 2020
Case study: check completeness of binary tree
Here is the gist.
The interviewee wrote the excellent idea to figure out the completeness of binary tree. His idea is to calculate total nodes in the binary tree first, and then assign each node with a value based on the structure of tree, the root node has value 0, and left child is parent node's value * 2 + 1, right child is parent node's value * 2 + 2. And then if it is a complete binary tree, all nodes value should be in the range of [0, totalNodes - 1]. Apply preorder travesal, and check if node's value is smaller than total nodes.
The interviewee wrote the excellent idea to figure out the completeness of binary tree. His idea is to calculate total nodes in the binary tree first, and then assign each node with a value based on the structure of tree, the root node has value 0, and left child is parent node's value * 2 + 1, right child is parent node's value * 2 + 2. And then if it is a complete binary tree, all nodes value should be in the range of [0, totalNodes - 1]. Apply preorder travesal, and check if node's value is smaller than total nodes.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment