Data Structures for Coding Interviews in C#/

...

/

Overview of Trees

Overview of Trees

A quick overview of trees, its types, and some important formulas to compute the height and number of nodes in a tree.

We'll cover the following...

Binary trees

Definition: A tree where each vertex has two children at most.

Types: Perfect, Full, Complete, and Skewed

Total number of nodes: 2(h+1)−12^{(h+1)}-1

Total number of leaf nodes: 2hor(n+1)22^{h} or \frac{(n+1)}{2}

Height: log2(n+1)−1log_{2}(n+1)-1

%0 1 1 2 2 1->2 3 3 1->3 4 4 2->4 null 5 2->null
Binary tree

Binary search trees

Definition: Every node has a value greater to all the node values in its left-subtree and has a value less than all the node values in the right-subtree. Mathematically:

Ke ...