# 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

&#x20;                 1(6)

&#x20;              /          \\

&#x20;          2(3)        3(0)

&#x20;         /      \\

&#x20;     4(1)     5(0)

&#x20;   /        \        \\

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
