Data Structures

Tree

Lesson

A tree stores data in layers. For example, a file system is a Tree:

Whenever someone says the word "tree", they're usually referring to the top node of the tree, called the "root". This is one of the largest confusions to beginners.

In an interview, you'll usually be given the simplest tree, a "Binary Tree". Each node in a Binary Tree has 2 children left and right and a value val.

We often draw the value $\small \tt val$ inside of each node (like above). But you should understand that $\small \tt val$ is a pointer just like $\small \tt left$ and $\small \tt right$ .

Time

Reading from a tree is slow, because you might need to step through many of the nodes. You always start at the root node and walk down to other nodes.

This means reading/writing is O(n), where n is the number of nodes in the tree.

Read/Write Time $O(n)$

You typically read/write faster, if the tree is balanced:

This is because the tree is spread "wider", so you have to take fewer steps down. A balanced tree has a height of $O(\log n)$ , so it takes $O(\log n)$ steps to reach an arbitrary element in it. See the spoiler for an explanation on why the height is $O(\log n)$ .

Open SpoilerClose Spoiler

In a balanced tree, every layer doubles in size.

This means if our tree is $h$ layers tall, the number nodes is roughly equal to all of the nodes in the bottom layer, which is $2^h$ .

\notag n = 2^{h}

We can use this equation to solve for the height of our tree, given the number of nodes we have. To do this, you take the log of both sides of the equation.

\notag \begin{align*} \log(n) &=\log( 2^{h})\\ &=h \end{align*}

This tells us that the number of layers in a balaned tree is $h = \log(n)$ .

Balanced Tree Height $O(\log n)$

$O(\log n)$ is really small.

This is because if n doubles in size, log(n) only increases by 1. For example:

\notag \begin{align*} &n = 1024\\ &\log(n) = 10\\[10 bp] &n = 2048 \\ &\log(n) = 11 \end{align*}

Mark as Completed:

Submits:

test

Imports:

TreeNode

Test your code to get an output here!