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.


No comments:

Post a Comment