Keep a count of nodes in left subtree with binary search tree

This comes up in Gayle Laakmann McDowell's book.

You need to have the number of nodes to the left of each node, and you want that updated with each insert.

This post is about doing this by walking down the tree as you do for BST insert.

One way is to just update each node to say the number of nodes in its subtree (including itself). When you add one node to the tree, this goes up by one at the current node, no matter if you walk left or right. The you check the left child to see how many a node has on the left.

The code in the book does it differently. It inserts a node into a binary tree but only increases the current nodes count if the node put in the left child.With all nodes inserted, the tree nodes then have a count of how many nodes are on the left of each node. It's sort of like letting marbles roll into position. At each node you watch how many end up rolling left, and then will end up being the number of left nodes.