# TechToolboxTuesday : Recursion on Trees

I love trees! They are so easy, so versatile, and if you understand the concept well, you can essentially solve any algorithmic question using the same technique. I was excited when I got a request to write a post about trees for the same reason - I can now share the technique with you and hopefully add to your toolbox! 😉

The reason recursion on trees is deceivingly simple to understand is that trees are naturally defined recursively. For the purpose of this post, I will assume that we are working with integer binary trees but the same ideas can be used on N-ary trees of other types as well. So a binary tree has a root node (which may or not have a value). If the root is not empty, it has 0, 1 or 2 children. Each child of the tree now repeats the same properties, i.e., if it has a value, it may have 0, 1 or 2 children , and so on. Can you now understand why I said trees are defined recursively naturally? Each child of a tree is a tree itself.

Now, there are 2 main models - and if you are able to understand these, solving most of the problems on trees becomes a cake walk 😉

1) Counting the number of nodes in a tree

2) Searching a node with some property in a tree

Before we get into the details of these two models, here is how we will define the node of a tree :

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

This is consistent with our recursive definition of the tree.

1) Counting the number of nodes in a tree

In the example above, the number of nodes in the tree with root = 1, is 5.

The number of nodes in the tree with root = 2, is 3.

The number of nodes in the tree with root = 3, is 1, and so on.

Looking at 3, we realize that the number of nodes in 3 is 1 because it does not have any children. Similarly, the number of nodes in 2 is 3 because it has 2 children + itself. Every recursive problem needs a base case, and this is ours. So now, writing the code for this problem becomes very easy :

def countNodes(tree):
    if tree is None: # empty tree : 0 nodes
        return 0
    elif tree.left is None and tree.right is None: # no children : 1 node
        return 1
    else: # more than one children : itself + number of nodes in both the children
        return 1 + countNodes(tree.left) + countNodes(tree.right)

This method can not only be used to count the number of nodes, but can be modified to count the number of leaves, nodes with certain properties such as a value > 15 etc.

2) Searching a node with some property in a tree

To make the explanation really simple, we are going to look for a node whose value is equal to a given value, return the Node if present, and None if not.

Going back to the same example tree - say the input tree is the one with the root node 1, and we have to look for a value “4”. 1 is not equal to 4, so you check if either of the children are equal to 4. Nope - so you further go and check the children of children and so on - do you feel a recursive solution coming in?

What will be our base case? 1) if we reach the leaf node and don’t find the value we are looking for. 2) we actually encounter a node who’s value is equal to the value we are searching for. Hence:

def searchNode(tree, val):
    if tree is None: # base case : we reach an empty node
        return None
    if tree.val == val: # base case : we found the value
        return tree
    # so far : haven't found the node
    x = searchNode(tree.left, val) # we search for the value in the left child
    y = searchNode(tree.right, val) # we search for the value in the right child

    if not x and not y: # if both the children return None, that means we have reached the end, and didn't find the value
        return None
    elif not x: # if only one returns None, we have found the value in the other child and can return it
        return y 
    elif not y:
        return x

As we will see in the LeetCode walkthrough tomorrow, most of the questions on Trees can be solved with little modification if you understand both of these models well. Let me know in the comments below how you like Trees as a data structure and if there is a particular LeetCode question you would like me to solve tomorrow!