How to represent a non binary tree and how to do LCA on that tree?

Question

How are non binary trees typically represented? Trees where there is no limit to the number of children a node can have. Is it best to use a Adjacency Matrix or Adjacency List and just assume there will be no cycles, or do something similar to this question ->

How to implement a Non-Binary tree

and follow up question, when you have a n-ary tree (is that the correct name for them?) What's a good way to find the Least Common Ancestor for two given nodes/data values in that tree? All I can find are algorithms that deal with binary trees, like this one ->

static Node lca(Node root,int v1,int v2)
{
  if (root == null || root.data == v1 || root.data == v2) {
    return root;
  }

  Node left = lca(root.left, v1, v2);
  Node right = lca(root.right, v1, v2);

  if (left != null && right != null) {
    return root;
  }

  return (left != null) ? left : right;
}

Gildagildas

Answer 1

Adjacency matrix sounds like a bad idea, it will be very sparse (most cells will be empty). Usually for n-ary trees (yes that's how they are called) you just follow the same strategy as with the binary tree, the difference is that a binary tree would have 2 fields representing the left and right children:

class Node<T> {
   T value;
   Node<T> left;
   Node<T> right;
}

Here you change those fields into a data structure like an array (static or dynamic):

class Node<T> {
   T value;
   List<Node<T>> children;
}

As for the LCA, are you planning on storing the parent pointer in the nodes? Are the values supposed to be a tree with unique values? Will the values be ordered in any way?

If no, but you can assume that the nodes are in the tree (although handling the other case is not that hard) then the LCA is very similar to what you've shown above. You just need to change the part where you get the Node left and Node right so that it traverses all children:

int count = 0;
Node<T> temp = null;
for(Node<T> child : root.children) {
    Node<T> result = lca(child, v1, v2);
    if(result != null) {
        count++;
        temp = result;
    }
}

if(count == 2) {
    return root;
}

return temp;

With parent pointers and/or storing the dept in each node we can do better but at a storage cost.

Andre

Great thread! Can you detail how would parent pointers and/or storing the dept of nodes speed up the algorith? The current implementation has O(n) time and O(1) space complexity? Is that correct? Thanks! – Unconcerned