Recursion

Given the root node of a binary tree `root`

, set every node's value to its depth*height. Do not return anything.

The depth and height are both indexed at 1.

**Example 1:**

**Explanation:** The root node has a depth of 1 and a height of 3. The middle node has a depth of 2 and a height of 2. The bottom node has a depth of 3 and a height of 1.

**Example 2:**

**Explanation:** The root node has a depth of 1 and a height of 2. The other nodes have a depth of 2 and a height of 1.

First Few Test Cases:

To solve this problem, the idea is to create a function that computes the depth and height at every node using recursion. Once you have that function, you can easily hijack it so that it also sets the depth*height of every node.

1. Recursion

You already know how to find the height of each node recursively. Here's the recursion:

We want to hijack the function to set the depth*height, like this:

The problem is we still haven't found a way to compute the `depth`

.
In order to compute the depth, you have to do something totally different from finding the height. This is because if you were given some random node in the tree, it's impossible to tell how deep it is. Nodes don't know anything about their parents or their location.

You need to pass the depth down from the parent nodes. To do this, you can add a new input to the function called `depth`

, which indicates the current depth the node is on. Whenever you call the function on a child node, you add 1 to the depth. Here's how you modify the recursion to do this:

This recursion goes through every node in the tree and computes its depth and height, just like we wanted.

2. Base case

The recursion will call itself on deeper and deeper nodes. Eventually, it gets to a node that's null, in which case the height is just 0.

3. Code

To code the function up, you just combine the recursion and base case. The function goes through every node in the tree and compute its `depth`

and `height`

, and we "hijack" it so that it also sets the `depth*height`

of every node.
We'll make sure that the value gets set on the last line, so that we're not changing the value under our own feet. It only gets set after it's already been used.

Time Complexity $O(n)$ since you walk through every node in the tree.

Space Complexity $O(n)$ due to the Call Stack.

In general, if you want to pass information down from parent nodes to children nodes, you need to add an input to your function.

Mark as Completed: