Problem
Given a binary tree, find the height of the tree. It is defined as the path with most number of nodes that start from root to any leaf.
For example:
Given tree
8
/ \
3 5
/
4
the out put is 2.
Solution
We can use post order traversal, at the parent node, we know stats of the subtree, so we can return the largest path length to the parent.
/*
Find the longest path in a tree
5
/ \
3 2 8
/ \ \
4 9
\
9
get(5)
1 + max(get(3), get(2)) <= 4
1 + max(get(4), get(9)) <= 3 , 1+max(0, 0) <= 1
1 + max(0, 1) = 2
*/
class LongestTreePath {
private static class Node {
private int value;
private Node left;
private Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
public static int getLongest(Node root) {
if(root == null) return 0;
return 1+ Math.max(getLongest(root.left), getLongest(root.right));
}
public static void main(String...args) {
Node root = new Node(5, new Node(3, new Node(4, null, null), new Node(9, null, null)), new Node(2, null, null));
System.out.println(getLongest(root) - 1);
}
}
Find the longest path in a tree
5
/ \
3 2 8
/ \ \
4 9
\
9
get(5)
1 + max(get(3), get(2)) <= 4
1 + max(get(4), get(9)) <= 3 , 1+max(0, 0) <= 1
1 + max(0, 1) = 2
*/
class LongestTreePath {
private static class Node {
private int value;
private Node left;
private Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
public static int getLongest(Node root) {
if(root == null) return 0;
return 1+ Math.max(getLongest(root.left), getLongest(root.right));
}
public static void main(String...args) {
Node root = new Node(5, new Node(3, new Node(4, null, null), new Node(9, null, null)), new Node(2, null, null));
System.out.println(getLongest(root) - 1);
}
}
We need to visit all nodes to find the stats, the time cost is O(N). The recursive call stack hight is proportional to tree hight, which is O(logN) in average. Each call stack has finite number of variables, so the space cost is O(logN).
