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 val\small \tt val inside of each node (like above). But you should understand that val\small \tt val is a pointer just like left\small \tt left and right\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)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(logn)O(\log n), so it takes O(logn)O(\log n) steps to reach an arbitrary element in it. See the spoiler for an explanation on why the height is O(logn)O(\log n).

Balanced Tree Height O(logn)O(\log n)

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

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

n=1024log(n)=10n=2048log(n)=11\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!