[Twitter] Count Visible Nodes in Binary Tree

Question

link

In a binary tree, if in the path from root to the node A, there is no node with greater value than A’s, this node A is visible. We need to count the number of visible nodes in a binary tree. For example, in the following tree:

		5
	 /     \
   3        10
  / \      /
20   21   1

There are four (4) visible nodes: 5, 20, 21, and 10.

Solution

This is an easy question. A solution is available here.

Code

written by me

public int countVisible(TreeNode root) {
	return helper(root, Integer.MIN_VALUE);
}

private int helper(TreeNode node, int ancesterMax) {
	if (node == null) {
		return 0;
	}
	int newMax = Math.max(ancesterMax, node.val);
	if (node.val > ancesterMax) {
		return 1 + helper(node.left, newMax) + helper(node.right, newMax);
	} else {
		return helper(node.left, newMax) + helper(node.right, newMax);
	}
}