CareerCup

int getHeight(TreeNode root){
	if(root == null || root.isLeaf() ) { return 0; }
	Map<TreeNode, Integer> children = new HashMap<>();
	int tallest = 0;


	for(TreeNode n: root.children()){
		children.put(n,getHeight(n));
		if(children.get(n) > tallest ){
 tallest = children.get(n);
 }
}
return tallest + 1;

Implementation in C#

public class TreeNode
        {
            public List<TreeNode> Children { get; set; }
        }
        public int GetMaxHeight(TreeNode node)
        {
            if (node.Children == null || !node.Children.Any())
            {
                return 1;
            }
            else
            {
                int tallestChild = 0;

                foreach (var child in node.Children)
                {
                    int childHeight = GetMaxHeight(node);
                    if (childHeight > tallestChild)
                    {
                        tallestChild = childHeight;
                    }
                }

                return tallestChild + 1;
            }
        }

/* 
ZoomBA : Using Level Order Traversal 
stackoverflow.com/questions/1894846/printing-bfs-binary-tree-in-level-order-with-specific-formatting
*/
def traverse(rootnode){
  thislevel = list( rootnode )
  height = 1 
  while ( !empty( thislevel ) ){ 
    nextlevel = fold( thislevel , list() ) ->
      $.p += list( $.o.children )->{ $.o }
    }
    thislevel = nextlevel
    height += 1 
  }
  height 
}

public static int getHeight(TreeNode root) {
	if (root == null) return 0;
	int maxHeight = 0;

	for(TreeNode n : root.childrens) {
		maxHeight = Math.max(getHeight(n), maxHeight);
	}

	return maxHeight + 1;
}

private int maxHeight = 0;


public int height(Node root){
	height(root, 0);


	return maxHeight;
}


private void height(Node node, int height){
	if(node != null){
		for(Node child : node.children)
			height(child, height + 1);
	}else{
		if(height > maxHeight)
			maxHeight = height;
	}
}

This is an Objective-C solution using recursion

-(int)getTreeHeigth:(TreeNode *)root{
    
    if(root == nil){
        return 0;
    }
    
    return fmax([self getTreeHeigth:root.left] + [self getTreeHeigth:root.rigth]) + 1;
}

calss TNode {
	int key;
	List<TNode> branches= new ArrayList<TNode>();

}
int Height()
{
	int max=0;
	for ( TNode n: this.branches)
	{
		if (  n!= null)
		{
			int h= n.Height();
			if ( h > max) max= h;
		}
			
	}
	return max + 1;

}

public int findHeight(Node root){
		int currentMax = 0;
		if(root==null){
			return 0;
		}
		if(root.children.size()==0){
			return 1;
		}
		for(Node n : root.children){
			int current = findHeight(n);
			if(current>currentMax){
				currentMax = current;
			}
		}
		return currentMax+1;

}

//Calculate height of n-ary tree
	public static int getHeight(TreeNode root){
		if(root == null){
			return 0;
		}
		
		int height = 0;
		if(root.getChildren() != null){
			for(TreeNode child : root.getChildren()){
				height = Math.max(height, getHeight(child));
			}
		}
		return height + 1;
	}

Recursive python implementation

class TreeNode:
	def __init__(self, value, args*):
		self.value = value
		self.children = [ x for x in args[1:]]

def getTreeHeight(root):
	if not root:
		return -1
	return max([getTreeHeight(x) for x in root.children]) + 1

To find max height of a tree - DFS algorithm should be used
NTreeGetHegiht.hpp

//
//  NTreeGetHeight.hpp
//  codility-lessons-refresh
//
//  Created by Przemek Urbanski on 17/11/16.
//  Copyright © 2016 Przemek Urbanski. All rights reserved.
//

#ifndef NTreeGetHeight_hpp
#define NTreeGetHeight_hpp

#include <stdio.h>
#include <list>
#include <vector>

using namespace std;

namespace NTreeGetHeight {
    class Graph {
    public:
        Graph(int elements);
        void addEdge(int parent, int child);
        int height();
    
    private:
        int travers(int nodeId, int nodeHeight);
        
    private:
        vector< list<int> > _nodes;
        int _height;
    };
};
#endif /* NTreeGetHeight_hpp */

NTreeGetHeight.cpp

#include "NTreeGetHeight.hpp"
#include <iostream>

using namespace std;

namespace NTreeGetHeight {
    
    Graph::Graph(int elements) {
        _nodes.resize(elements);
        _height = 0;
    }
    
    void Graph::addEdge(int parent, int child) {
        _nodes[parent].push_front(child);
    }
    
    int Graph::height() {
        // for graph with nodes count 0, 1, 2
        // its height is equal to its node cound.
        if (_nodes.size() < 3 )
            return _nodes.size();
        
        travers(0, 0);
        return _height;
    }
    
    int Graph::travers(int nodeId, int nodeHeight) {
        for (auto node : _nodes[nodeId] ) {
            _height = max( travers(node, nodeHeight+1), _height);
        }
        
        // There is a bit of optimization can be done here.
        // Keep track of visited node count.
        // Then if ( total_graph_nodes_count - visited_nodes_count <= _height )
        // you can stop traversing. As there is not enough unvisited nodes which can beat
        // current _height;
        return nodeHeight;
    }
};

Test

#include <iostream>

using namespace std;
using namespace NTreeGetHeight;

int main() {
    Graph ntree(11);
    
    ntree.addEdge(0,1);
    ntree.addEdge(0,9);
    ntree.addEdge(0,4);

    ntree.addEdge(1,2);
    ntree.addEdge(1,3);

    ntree.addEdge(9,10);

    ntree.addEdge(10,5);

    ntree.addEdge(5,6);
    ntree.addEdge(5,7);
    ntree.addEdge(5,8);
    
    cout << ntree.height();
    
    return 0;
}

Is the tree balanced? If so wouldn't it just be log_n(N)?

def height_n_ary(tree):
    if tree:
        return 1 + max(height_n_ary(x) for x in tree.children)
    return 0

O(n)

int getHeight(Node root) {
	if (root == null) {
		return 0; 
	}

	int height = 0;
	for (int i = 0; i < root.children; i++) {
		height = max(height, getHeight(root.children[i]));
	}

	return height + 1;

}