Find out if a node is an ancestor of another node in a binary tree

Question

I need to add a constant amount of fields to each node in the tree, so that when given two nodes x, y, I need to find out if x is an ancestor of y in O(1) complexity.

My first thought was to add a "depth" field to each node. Then I can straight on eliminate queries if x.depth >= y.depth, but this is obviously not enough...

score 1 · Answer 1 · 2018-04-27T11:28:42.800

Let's say you build a tree:

              a
             / \
            /   \ 
           /     \
          b       c
        /  \     / \
       /    \   /   \
      d      e f     g
      \             /  \
       h           i    j
       /
      k

Each node has an additional field, an uint32_t int lineage. If you are implementing the tree with an array this extra field is unnecessary. For all intents, and purposes, assume we are using nodes.

You can use the idea similar to:

left  = 2 * parent + 1;
right = 2 * parent + 2;

But, instead, at the root node, let lineage equal 1. For all subsequent nodes, you insert normally, also passing the lineage. This will be an integer, but you will do bitwise arithmetic on it. If you go left, you simply shift to the left (multiply by 2), if you go to the right, shift left + 1.

/**
 * Starts recursive insertion
 */
struct node* insert(struct node* node, int key) {

  // Create root
  if (node == NULL) {

    // Root has value 1
    node = newNode(key, 1);

  // Start recursion to left
  } else if (key < node->key) {

    node->left = insert(node->left, key, node->lineage << 1);

  // Start recursion to right
  } else if (key > node->key) {

    node->right = insert(node->right, key, (node->lineage << 1) + 1);
  }

  return node;
}

/**
 * Recursive insert function
 */
struct node* insert(struct node* node, int key, uint32_t lineage) {

    if (node == NULL) {

      return newNode(key, lineage);
    }


    if (key < node->key) {
      node->left  = insert(node->left, key, 2 * node->lineage);
    }

    else if (key > node->key) {
      node->right = insert(node->right, key, 2 * node->lineage + 1);
    }

    return node;
}

Essentially you create a binary patterns. If you look at your tree in terms of the binary lineages, it will be this:

              1
             / \
            /   \ 
           /     \
          /       \
         10       11 
        /  \      / \
       /    \    /   \
     100   101 110   111
      \             /  \
     1001         1110  1111
       /
    10010

Or more simply:

              1
             / \
            /   \ 
           /     \
          /       \
         1L       1R 
        /  \      / \
       /    \    /   \
     1LL   1LR 1RL   1RR
      \             /  \
     1LLR        1RRL  1RRR
       /
    1LLRL

Whether you call them Ls and Rs or 1s and 0s, we know for a node to be an ancestor or a node, the binary lineage (or L R pattern) must be a sub-string of the child node, going from left to right, with the condition that the ancestor's binary string is strictly less than that of the child.

However, we used integers instead of strings so that we can figure out if it is a substring in constant time.

Important part

// Calculate if ancestor in O(1), no loops, no recursion
bool is_ancestor(struct node* parent, struct node* child) {

  // Both pointers must be non-null
  if (parent == NULL || child == NULL) {

    return false;
  }

  // Get their lineages
  uint32_t p_lin = parent->lineage;
  uint32_t c_lin = child->lineage;

  // Calculate the number of bits in
  // binary lineage number
  int p_bits = log2(p_lin);
  int c_bits = log2(c_lin);

  // Ancestors must
  // have less bits than
  // children. If this is false,
  // than the parent pointer
  // is at a lower point in the tree
  if (p_bits >= c_bits) {

    return false;
  }

  // Calculate difference in bits
  // which represents the number of
  // levels in between the child and parent
  int diff = c_bits - p_bits;

  // Shift child lineage to
  // the right by that much
  // to get rid of those bits, and
  // only leave the amount of
  // bits they should have in
  // common
  c_lin >>= diff;

  // First N bits should be
  // exactly the same
  if (c_lin == p_lin) {

    return true;
  }

  // If we got here, the child`
  // is lower in the tree, but
  // there is no path from the
  // ancestor to the child
  return false;

}

Here is log2() in O(1) from: What's the quickest way to compute log2 of an integer in C#?

int log2(uint32_t n) {

  int bits = 0;

  if (n > 0xffff) {
    n >>= 16;
    bits = 0x10;
  }

  if (n > 0xff) {
    n >>= 8;
    bits |= 0x8;
  }

  if (n > 0xf) {
    n >>= 4;
    bits |= 0x4;
  }

  if (n > 0x3) {
    n >>= 2;
    bits |= 0x2;
  }

  if (n > 0x1) {
    bits |= 0x1;
  }

  return bits;
}

Use:

#include <stdio.h>
#include <stdlib.h>
#include <cstdint>

#include "tree.c"  // Your tree

int main() {

  /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
    struct node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("preorder:\n");

    preorder(root);

    struct node* parent  = get(root, 30);
    struct node* child   = get(root, 40);

    bool ancestor = is_ancestor(parent, child);

    printf("\n %d is a child or %d: %d\n", parent->key, child->key, ancestor);


    return 0;
}

Output:

preorder:
k: 50 lineage: 1
k: 30 lineage: 2
k: 20 lineage: 4
k: 40 lineage: 5
k: 70 lineage: 3
k: 60 lineage: 6
k: 80 lineage: 7

 30 is a child or 40: 1

If it's any use, I can give you the full code, the tree.c so you can try it yourself. This is just an idea that I tried on a small tree. Sorry for the long explanation, but I too was interested in the problem.

Find out if a node is an ancestor of another node in a binary tree

1 Answers1

Important part