# Tree Traversal

This note is prompted by this question: https://leetcode.com/problems/same-tree/

This note covers how to traverse a binary tree with recursion.

## Tree Basics

Trees are an Abstract Data Type composed of a set of nodes connected by a set of edges. Between any two nodes there will only be one path, so there are no cycles in a tree.


**Root Node**: A rooted tree is one where every node with the exception of the “root” of the tree has one parent. The “root node” has no parents.

**Leaf Node**: A leaf node is a node that has no children.

**Binary Tree**: Every node in the tree can have 0, 1, or 2 children.

**TreeNode Implementation**

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
if __name__ == "__main__":
    root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(8)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(7)
    root.right.right = TreeNode(10)

Notice how we can use the TreeNodes to create a Tree, very much like we use Links to create a Linked List.

## Binary Tree Traversal

Before we get to the Leetcode problem, let me pose two easier:

### Problem 1
1. How do we write a function that prints the values of the tree in the same order that we would get from reading the nodes from left to right. Using the above tree, the **inorder** values: 1, 3, 4, 5, 7, 8, 10

#### Brainstorming

Let's consider using normal iteration. We can iterate down to the leftmost node and print it, but then how do we get back up the tree without a pointer to the parent node? I guess we could keep a record of where we've been, but is it possible to do it without explicitly keeping a record?

I don't know of a way (btw if you know how to do this, please comment below and teach me).

So since interation doesn't seem to have an easy solution, what if we considered a recursive solution? Is it possible? The tree structure does seem recursive in nature. Let's try it.

#### "Pseudocoding"

1. What is the base case?
The simplest case of this problem would be if the tree they gave us was an empty tree. In other words, the input is `None`. Hmmm what about checking the left node and the right node to see if their `None` as well? No! That's Arms Length Recursion.

2. What is the recursive case?
For every node, there are two children that I have to solve the same problem of printing in order for. Seems recursive. I also have to print the current node's value.

Let's see if we can code it up:

def inorder(node):
    if node is None:
        return
    else:
        inorder(node.left)
        print(node.val)
        inorder(node.right)

And that's it!

Notice something here: **Arms Length Recursion**
When writing this function, your initial instinct may be to check if the left node is None or the right Node is None.

DON’T DO IT!!! [Professor Hug](https://www2.eecs.berkeley.edu/Faculty/Homepages/joshhug.html) called this arms length recursion because you stop the recursion when you are arms length away from the base case. It is a bad practice for these [reasons](https://www.quora.com/What-is-arms-length-recursion?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa).

Allow the recursion to go all the way through. Rather than checking the children, allow the recursion to go to the children. Then check the current node.

### Problem 2
2. How do we write a function that checks if a tree has a particular value?

#### Brainstorming
Recursion seemed to work well and is pretty simple for the last one, so let's try it again.

#### "Pseudocoding"

What is the base case?
- The simplest case of this problem would be if the tree they gave us was an empty tree.

What is the recursive case?
- For every node, there are two children that I have to solve the same problem checking if the current node is the value I'm looking for. When my current node doesn't have the value I have to consider my left children and right children.

Note how we use thee return value of the recursive call to "collect" the solution after the recursive call has completed the call. `

Let's see if we can code it up:

def has_val(node, val):
    if node is None:
        return False
    else:
        left_has_val = has_val(node.left, val)
        cur_val = node.val == val
        right_has_val = has_val(node.right, val)
        return left_has_val or cur_val or right_has_val

**Note** that this function can be written cleaner. I've written it as such b/c it's easier to understand.

Now we are ready to tackle the problem below.

## The Problem
Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true
Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false
Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

The program takes two arguments `p` and `q`

### Brainstorming

We need to figure out if the problem is **structurally identical**. So let's get into the details and understand what this means.

For each node there are the following possibilities:
1. One tree may have a node that the other does not have. (Example 2) In other words, the "structure" of the tree is different.
2. Both trees have the node, but the values differ (Example 3) In other words, the "content" of the tree is different.

So if we want to determine if the two trees are different, we need to check for both structure and content.

We know how to traverse one tree, so can we traverse both trees in the same way? For example if in one tree we would have gone left by making the recursive call to the left node, then in both tree `p` and tree `q` we go left. When we would have gone right in the single tree by making the recursive call to the right node, then in both tree `p` and tree `q` we go right.

As we traverse the two trees together, we could compare the "content" of the two nodes from both of the trees. If one of the tree doesn't have the node, then we know that the "structure" of the tree is different.

This idea seems promising. Let's pseudocode it.

### "Pseudocoding"

What are the base cases?
1. The obvious simplest case is if the tree is empty. But now we have two trees. So let's consider the possibilities:
1.1. Both trees are empty, then the structure and the value are technically the same. So we'll want to return `True`
1.2. Tree `p` is empty and tree `q` is not. Then the structure is not the same. So we'll want to return `False`
1.3. Tree `q` is empty and tree `p` is not. Then the structure is not the same. So we'll want to return `False`

2. What is the recursive case?
For every node, there are two children that I have to solve the same problem for, so I'll be recursing on them. This time I have to recurse on both of the trees.

I also have to compare if the node in both of the trees are equal.

Let's see if we can code it up:

def isSameTree(p, q):
    if p is None and q is None:
        return True
    elif p is None:
        return False
    elif q is None:
        return False
    else:
        left_is_same = isSameTree(p.left, q.left)
        cur_is_same = p.val == q.val
        right_is_same = isSameTree(p.right, q.right)
        return left_is_same and cur_is_same and right_is_same

**Note**: In problem 2, we used `or` because as long as one node had the value we were looking for, the solution is `True`, then the solution was `True`. In this problem, if one node doesn't match up structurally or contextually, then the solution is `False`

This will allow us to clean up our code and make it a bit more efficient:

def isSameTree(p, q):
    if p is None and q is None:
        return True
    elif p is None:
        return False
    elif q is None:
        return False
    return p.val == q.val and \
            isSameTree(p.left, q.left) and \
            isSameTree(p.right, q.right)

**Note**: I put `p.val == q.val` ahead of the recursive call in hopes of saving some function call by *short circuiting*.

<style>
body > .ui-infobar, body > .ui-toc, body > .ui-affix-toc {
display: none !important;
}
</style>