Binary Tree

Definition

• Is a Tree like data structure where every node has at most two children.
  • There is one left and right child node.

What you need to know

• Designed to optimize searching and sorting.
• A degenerate tree is an unbalanced tree, which if entirely one-sided, is essentially a linked list.
• They are comparably simple to implement than other data structures.

How many nodes are there in a balanced binary tree?

This is important to reason out, as opposed to taking it for granted. Used for reasoning out Segment Tree.

0th level has one node, 1st-level has two nodes, 2nd level has 4 nodes, … i-th level has $2^i$ nodes.

In total, we have at most $2^0+2^1+\cdots +2^h=2^{h+1}-1$ nodes (see Geometric Series formula), where $h$ is the height of the tree, $h=\lceil log(n)\rceil$.

• The last layer has at most $2^h$ nodes, it is $2^h$ when it is completely filled as a row.
• Also, I defined $n$ as the number of leaf nodes that you want to represent, because I was doing Segment Tree analysis

So we can actually solve this,

$2^{h+1}-1=2^{\lceil {\log }_{2}n\rceil +1}-1=2\cdot 2^{\lceil {\log }_{2}n\rceil }-1\le 2(2n)-1=4n-1$ If it is a perfectly balanced tree, so ${\log }_{2}n=h$, then you have exactly $2n-1$ nodes.

So there are at most $4n-1$ total nodes in a balanced binary tree!

• A segment tree actually uses at most $2n-1$, but we create an array of $4n$ to fully fill the last layer of the tree.
• See https://cp-algorithms.com/data_structures/segment_tree.html#memory-efficient-implementation

How do you prove that there are at most $2n-1$ nodes used for segment tree?

• There are $n$ leaf nodes
• A binary tree with $n$ leaf nodes has $2n-1$ total nodes

Can you bound it by 2n?

Seems like i was able to. That’s also why Segment Tree has $2n$ number of nodes implementation. There is a more careful analysis. Because the $2^{h+1}-1$ analysis actually assumes that all the layers are filled.

What is 2^{\lceil \log_2 n \rceil}?

Answer: $2n$. $\lceil {\log }_{2}n\rceil$ gives us the smallest number $x$ such that $2^x\ge n$. We have two cases:

1. $n$ is a power of two, so $2^x=n$
2. $n$ is not a power of two, so $2^x>n$, where $x$ is the smallest power.

Ex: For $n=9$, we would have $x=4$. Then, $2^{\lceil {\log }_{2}n\rceil }=2^x$ which is the smallest power of 2 that is greater of equal to $n$. For $n=22$, that is $2^5=32$.

We can see more generally, that $2n$ always works.

Related

• Segment Tree