Non-binary tree height

Question

Is there a way to find the height of a tree which is not necessarily binary? There are many algorithms for the height of a binary tree but none of them will work for a non-binary.

Answer 1

Solution in Python3:

class Graph:
    def __init__(self):
        self.nodes = dict()
        self.h = 0
        
    def addEdges(self, s, d):
        if s in self.nodes:
            self.nodes[s].append(d)
        else:
            self.nodes[s] = [d]
        
    def height(self, node):
        if node not in self.nodes:
            return 0
        self.h = 0
        
        for i in self.nodes[node]:
            self.h = max(self.h, self.height(i))
        
        return self.h+1
        
if __name__ == "__main__":
    graph = Graph()
    count = int(input())
    
    for i in range(count - 1):
        s, d = input().split()
        graph.addEdges(int(s), int(d))
    
    print(graph.height(1))

Test:

8
1 2
1 3
3 4
3 5
3 6
2 7 
2 8

Answer 2

It is possible. We can do by below approach.

package com.ds;

import java.util.Arrays;

public class TreeNode {

    private Integer data;
    private TreeNode[] children;

    public TreeNode() {
        super();
    }

    public TreeNode(Integer data) {
        super();
        this.data = data;
    }


    public void setChildren(TreeNode[] children) {
        this.children = children;
    }

    public Integer maxDepth(TreeNode treeNode) {
        Integer depth = 0;
        if (treeNode.children != null) {
            if (treeNode.children.length == 0) {
                return depth;
            } else {
                for (int i = 0; i < treeNode.children.length; i++) {
                    depth = Math.max(depth, this.maxDepth(treeNode.children[i]));
                }
                return depth + 1;
            }
        } else {
            return depth;
        }
    }

    @Override
    public String toString() {
        return "TreeNode [data=" + data + ", children=" + Arrays.toString(children) + "]";
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);
        TreeNode t9 = new TreeNode(9);
        TreeNode t10 = new TreeNode(10);
        TreeNode t11 = new TreeNode(11);
        TreeNode t12 = new TreeNode(12);

        TreeNode t101 = new TreeNode(101);

        TreeNode[] childOf1 = { t2, t3 };
        TreeNode[] childOf2 = { t4, t5, t101 };
        TreeNode[] childOf3 = { t6, t7 };
        TreeNode[] childOf4 = { t8, t9 };
        TreeNode[] childOf6 = { t10 };
        TreeNode[] childOf10 = { t11, t12 };
        t1.setChildren(childOf1);
        t2.setChildren(childOf2);
        t3.setChildren(childOf3);
        t4.setChildren(childOf4);
        t6.setChildren(childOf6);
        t10.setChildren(childOf10);

        TreeNode obj = new TreeNode();
        Integer depth = obj.maxDepth(t1);
        System.out.println("Depth- " + depth);

    }

}

Answer 3

Yes, there is. A recursive approach could be something like:

public class TreeNode<T>{
    private List<TreeNode<T>> children = new ArrayList<TreeNode<T>>();
    private T data = null;

    public TreeNode(T data){
        this.data = data;
    }       

    public List<TreeNode<T>> getChildren(){
        return children;
    }   

    public void setChild(TreeNode<T> children){
        this.children.add(children);
    }   

    public Integer getHeight(TreeNode<T> root){
        if(root == null) return 0;
        Integer h=0;

        for(TreeNode<T> n : root.getChildren()){
            h = Math.max(h, getHeight(n));
        }
        return h+1;
    }
}

Test:

public static void main(String[] args){
    TreeNode<Integer> root = new TreeNode<Integer>(50);
    TreeNode<Integer> c1 = new TreeNode<Integer>(100);
    TreeNode<Integer> c2= new TreeNode<Integer>(10);
    TreeNode<Integer> c3 = new TreeNode<Integer>(-5);
    TreeNode<Integer> c4 = new TreeNode<Integer>(0);
    TreeNode<Integer> c5 = new TreeNode<Integer>(33);
    TreeNode<Integer> c6 = new TreeNode<Integer>(1);
    TreeNode<Integer> c7 = new TreeNode<Integer>(2);
    TreeNode<Integer> c8 = new TreeNode<Integer>(3);
    TreeNode<Integer> c9 = new TreeNode<Integer>(300);
    TreeNode<Integer> c10 = new TreeNode<Integer>(350);

    root.setChild(c1);
    root.setChild(c2);
    c2.setChild(c3);
    c3.setChild(c4);
    c3.setChild(c5);
    c3.setChild(c6);
    c3.setChild(c7);
    c3.setChild(c8);

    c1.setChild(c9);
    c1.setChild(c10);

    System.out.print("Pre order: \n");
    root.dfs(root, 0);
    System.out.print("\nPost order: \n");
    root.dfs(root, 1);
    System.out.print("\nBFS: \n");
    root.bfs(root);
    System.out.println();
    System.out.print("\nHeigth: \n");
    System.out.println(root.getHeight(root));
}

Result:

Heigth: 
4

EDIT: Returns 4, instead of 3 as stated earlier

Answer 4

Generally, you can extend most of algorithms for binary tree to non-binary.

For example, for 2-tree:

h(node) = max(h(left-child-of(node)) , h(right-child-of(node)))+1

which can be extended to:

h(node) = max(h(for-all-child-of(node)) + 1

Answer 5

The definition is the same for any tree. The height of a tree is the height of any of its children (plus one). So if you have three children you check all three of them and take the greatest + 1 as your height, recursively.