Find the missing value in a complete BST populated by each numbe

ghz 8months ago ⋅ 117 views

Find the missing value in a complete BST populated by each number from 1 to 2^K, where K is the number of levels

Let K be the number of levels in a binary search tree. Hence, the maximum number of nodes I can have is (2^K)-1. I have a complete binary tree (i.e., to say that each level is completely filled), whose nodes are filled with each value from 1 to (2^k), without duplication. Since there are (2^K)-1 available nodes to be filled, but 2^K available values, there must be one value between 1 and (2^K) missing from the binary search tree. Help me design an algorithm to find that missing value. It should be in O(K) time complexity. Essentially, by just traversing each level once.

This is one of my assignment problems for DSA. I have a good implementation using in-order traversal, but that is not O(K), but instead O(2^K)/O(n). I am just not sure if this is even doable in O(K) time complexity.

For instance, for K=4, I fill in the binary tree with values from 1 to 2^4=16. But there are only 15 nodes, hence one is left out. In the example below, I leave out 14. How can I detect that 14 is missing in O(K) time?

            8                         k=1
          /   \
         4     12                     k=2
        / \    /  \
      2    6   10   15                k=3
     / \  / \  / \   / \
     1 3  5 7  9 11 13 16             k=4

Answers

To find the missing value in the complete binary tree efficiently in O(K) time complexity, we can exploit the properties of the binary search tree and the characteristics of the complete binary tree.

Here's an algorithm to achieve this:

  1. Initialize a variable missing to 0.
  2. Start traversing the tree from the root.
  3. At each level k, check if the left subtree is complete (contains 2^(k-1) nodes). If it is complete, the missing value cannot be in this subtree, so move to the right subtree. If it's not complete, move to the left subtree.
  4. Update the value of missing accordingly:
    • If you move to the left subtree, update missing by adding 2^(k-1).
    • If you move to the right subtree, no update is needed.
  5. Repeat steps 3-4 until you reach the leaf level.

Here's a Python implementation of the algorithm:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def find_missing(root, K):
    missing = 0
    node = root
    for k in range(1, K+1):
        # Check if left subtree is complete
        left_subtree_size = 2**(K - k)
        if is_complete(node.left, left_subtree_size):
            # Move to right subtree
            missing += left_subtree_size
            node = node.right
        else:
            # Move to left subtree
            node = node.left
    return missing

def is_complete(node, size):
    # Check if subtree contains 'size' nodes
    if node is None:
        return size == 0
    return is_complete(node.left, size - 1) and is_complete(node.right, size - 1)

# Example usage:
# Create the binary tree
root = TreeNode(8)
root.left = TreeNode(4)
root.right = TreeNode(12)
root.left.left = TreeNode(2)
root.left.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(15)
root.left.left.left = TreeNode(1)
root.left.left.right = TreeNode(3)
root.left.right.left = TreeNode(5)
root.left.right.right = TreeNode(7)
root.right.left.left = TreeNode(9)
root.right.left.right = TreeNode(11)
root.right.right.left = TreeNode(13)
root.right.right.right = TreeNode(16)

K = 4  # Height of the binary tree
missing_value = find_missing(root, K)
print("Missing value:", missing_value)

This algorithm ensures that we traverse each level of the tree only once, resulting in O(K) time complexity.

#algorithm