How to represent a non-binary tree and how to make LCA on this tree?

Question

How are non-binary trees usually displayed? Trees where there are no restrictions on the number of children that a node can have. It’s best to use the Adjacency Matrix or Adjacency List and just assume that there will be no loops or something similar to this question →

How to implement a non-binary tree

and the next question, when do you have an n-ary tree (is that the right name for them?) What is a good way to find the smallest common ancestor for two given node / data values ​​in this tree? All I can find are algorithms that deal with binary trees such as this ->

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; } 

Answer 1

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

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

Here you change these fields into a data structure such as an array (static or dynamic):

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

As for LCA , do you plan on storing the parent pointer in nodes? Do values ​​mean like a tree with unique values? Will the values ​​be ordered in any way?

If not, but you can assume that the nodes are in the tree (although handling the other case is not so difficult), the LCA is very similar to what you showed above. You just need to change the part where you get Node left and Node right so that it goes through all the 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 department storage in each node, we can do better, but at the cost of storage.