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 

The following pseudo-code is self-explanatory and it clearly runs in O(K):

findMissing(node)
  if isLeaf(node) {
    if node.value % 2 == 0
      return node.value - 1
    else
      return node.value + 1
  }
  else {
    if node.value % 2 == 0
      return findMissing(node.rightChild)
    else
      return findMissing(node.leftChild)
  }

The intuition is that, given a fixed K, each node in the tree can only have two possible values. For instance, when K=4, the root can be either 8 or 9, the leftmost leaf can be either 1 or 2, etc. Therefore, we can exploit the parity of the node's value for guessing which subtree is the "unbalanced" one.