Set left node count

Given a binary tree, count the number of nodes in each node’s left subtree, and store it in the numNodesLeft field.

Examples

1(6)

/ \

2(3) 3(0)

/ \

4(1) 5(0)

/ \ \

6(0) 7(0) 8(0)

The numNodesLeft is shown in parentheses.

Solution: sinking check, backtracking

Base Case: if root is null, return 0;

Recursive call:

From children: get left and right count

For self: pass up left + right count + 1

/**
 * public class TreeNodeLeft {
 *   public int key;
 *   public TreeNodeLeft left;
 *   public TreeNodeLeft right;
 *   public int numNodesLeft;
 *   public TreeNodeLeft(int key) {
 *     this.key = key;
 *   }
 * }
 */

public class Solution {
  public void numNodesLeft(TreeNodeLeft root) {
    numLeft(root);
  }

  public int numLeft(TreeNodeLeft root){
    if (root == null) return 0;
    int leftCount = numLeft(root.left);
    int rightCount = numLeft(root.right);
    root.numNodesLeft = leftCount;
    return leftCount + rightCount + 1;
  }
}

Time Complexity: O(2^N) two recursive calls per node

Space Complexity: O(Height) recursive call stack