C++ Intro

  1. C++ is a strongly-typed programming language where every variable has a type, name, value and location in memory.
  2. The type of a variable defines the contents of the variable. Every type is either:
    1. Primitive
    2. User-defined
  3. Primitive types:
    1. int
    2. char
    3. bool
    4. float
    5. double
    6. void
  4. User-Defined types:
    1. std::string
    2. std::vector
    3. many more
  5. C++ Programs
    • by c++ standard, it starts with a function int main() return value 0 indicate the program was successful.

      C++ Classes

  6. C++ classes encapsulate data and associated functionality into an object
    class Cube {
     double getVolume();
     double length_;
  7. data and functionality are separated into two separate protections: public and private
    • public members can be accessed by client code
    • private members can be accessed within the class itself
  8. the interface/header (.h file) to the class is defined separately from the implementation (.cpp file)
  9. C++ Header File (.h) defines the interface to the class, which include:
    • declaration of all member variables
    • declaration of all member functions
      class Cube {
       double getVolume();
       double getSurfaceArea();
       void setLength(double length);
       double length_;
  10. C++ Implementation File (.cpp) contains the code to implement the class
    #include "Cube.h"
    double Cube::getVolume() {
      return length_ * length_ * length_;
    double Cube::getSurfaceArea() {
      return 6 * length_ * length_;
    void Cube::setLength(length) {
      length_ = length;

    Example client program ```cpp #include “Cube.h”

int main() { Cube c;

c.setLength(3.48); double volume = c.getVolume(); std::cout « “Volume: “ « volume « std::endl; return 0 }

## C++ Standard Library (std)
Standard Library Organization
+ eg: iostream - includes operations for reading and writing to files and console, eg `std::cout`
#include <iostream>

int main() {
  std::cout << "Hello World!" << std::endl;
  return 0;
  • functionalites from the standard library will be part of the std namespace.
  • namespaces are used to avoid name conflicts for commonly used names.
  • we can import functions into the global space with using ```cpp #include

using std::cout; using std::endl; int main() { cout « “Hello World!” « endl; return 0; };

+ put our `Cube` class into an unique namespace
The header fiile `Cube.h`
namespace uiuc {
  class Cube {
      double getVolume();
      double getSurfaceArea();
      void setLength(double length);
      double length_;

The implementation file Cube.cpp

#include "Cube.h"
namespace uiuc {
  double Cube::getVolume() {
    return length_ * length_ * length_;
  double Cube::getSurfaceArea() {
    return 6 * length_ * length_;
  void Cube::setLength(length) {
    length_ = length;

Stack Memory and Pointers

In C++, the programmer has control over the memory and lifecycle of every variable.

  1. Stack memory
    • By default, variables live in stack memory.
    • & operator returns the memory address of a variable. ```cpp #include

int main() { int num = 7; std::cout « “Value: “ « num « std::endl; std::cout « “Address: “ « &num « std::endl; return 0; };

Value: 7
Address: 0x7ffc79466564
  • Stack memory is associated with the current function and the memory’s lifecycle is tied to the function.
    • When the function returns or ends, the stack memory of that function is released.
    • Stack memory always starts from high addresses and grows down. ```cpp #include

int main() { int num_1 = 7; std::cout « “Value: “ « num_1 « std::endl; std::cout « “Address: “ « &num_1 « std::endl; int num_2 = 1; std::cout « “Value: “ « num_2 « std::endl; std::cout « “Address: “ « &num_2 « std::endl; return 0; };

Value: 7
Address: 0x7ffd9b4eb780
Value: 1
Address: 0x7ffd9b4eb784
  1. Pointer
    • A pointer is a variable that stores the memory address of the data
    • simply put: pointers are a level of indirection from the data + In C++, a pointer is defined by adding an * to the type of the variable
    • Integer pointer: int * p = &num; here int * denotes the variable p is of interger pointer type and the value is the memeory address of num.
  2. Dereference Operator
    • Given a pointer, a level of indirection can be ren the dereference operator * ```cpp #include

int main() { int num = 7; int * p = &num; int q = *p;

std::cout « “value of num is “ « num « std::endl; std::cout « “q is “ « q « std::endl; std::cout « “p is “ « p « ” the address of num.” « std::endl; std::cout « “&p is “ « &p « ” the address of p.” « std::endl; std::cout « “*p is “ « *p « ” gives the value of num.” « std::endl;

p = 42; std::cout « “value of num is “ « num « std::endl; std::cout « “q is “ « q « std::endl; std::cout « “p is “ « p « ” the address of num.” « std::endl; std::cout « “&p is “ « &p « ” the address of p.” « std::endl; std::cout « “p is “ « *p « ” gives the value of num.” « std::endl;

return 0; };

puzzle - `g++ code.cpp` will throw errors and not build. Even with the class makefire it builds, executing the binary will cause seg fault.
#include <iostream>
#include "Cube.h"
using uiuc::Cube;

Cube *CreateUnitCube() {
  Cube cube;  // cube is stack allocated instance of class Cube.
  return &cube;  // return address of this stack allocated object
}  // once the function ends, the stack memory is released, meaning code executed after the function call may reuse the memory address for cube and write values to it. 

int main() {
  Cube *c = CreateUnitCube();  // pointer c points to an address that maybe overwritten anytime
  double a = c->getSurfaceArea();
  std::cout << "Surface Area: " << a << std::endl;  // if it even gets excuted, will unlikly output the area
  double v = c->getVolume();
  std::cout << "Volume: " << v << std::endl;
  return 0;

// Some other function that does something that uses some stack memory.
// In this code, we calculate the total volume of cubes of length from 0..99.
double someOtherFunction() {
  Cube cubes[100];
  double totalVolume = 0;

  for (int i = 0; i < 100; i++) {
    totalVolume += cubes[i].getVolume();

  return totalVolume;

Heap Memory

  1. Heap memory
    • Heap memory allows us to create memory independent of the lifecycle of a function.
    • The only way to create heap memory in C++ is with the new operator.
  2. new operator
    • The new operator returns a pointer to the memory storing the data - not an instance of the data itself.
    • The new operator will always do three things:
    1. allocate memory on the heap for the data structure
    2. initialize the data structure
    3. return a pointer to the start of the data structure + The memory is only ever reclaimed by the system when the pointer is passed to the delete operator ```cpp int * numPtr = new int;
  3. allocate integer pointer numPtr on the stack
  4. allocate integer on the heap */ ```
  5. nullptr
    • C++ nullptr is a pointer that points to the memory address 0x0
    • Address 0x0 is reserved and never used by the system
    • Address 0x0 will always generate an ‘segmentation fault’ when accessed
  6. -> Arror Operator
    • c->getVolume() is identical to (*c).getVolume()
    • (*c) is dereferencing the pointer to get the instance, then call the member function via .
    • -> is syntatical sugar

      Class Constructors

      When an instance of a class is created, the class constructor sets up the initial state of the instance.

  7. Automatic Default Constructor
    • If we do not provide any custom constructors, the C++ compiler provides an automatic default constructor for our class for free.
    • The automatic default constructor will only initialize all member variables to their default values.
    • But if we define any custom constructor, the automatic default constructor will not be provided by complier.
  8. Custom Default Constructor:
    • A member function with the same name of the class
    • The function takes zero parameters
    • The function does not have a return type ```cpp class Cube { public: Cube(); // custom default constructor

private: double length_; }

#include "Cube.h"

// custom default constructor
Cube::Cube() {
  length_ = 1;
  1. Custom Constructors
    • non-default custom constructors require client code to supply arguments:
      Cube::Cube(double length) {
        length_ = length;

      Copy Constructors

      In C++, a copy constructor is a special constructor that exists to make a copy of an existing object.

  2. Automatic Copy Constructor
    • If we do not provide a custom copy constructor, the C++ compiler provides an automatic copy constructor for our class for free.
    • This free automatic copy constructor will copy the contents of all member variables.
  3. Custom Copy Constructor
    • Is a class constructor
    • Has exactly one argument that is const reference of the same type
      Cube::Cube(const Cube & obj) {
        length_ = obj.length_;
  4. Copy Constructor Invocation Often copy constructors are invoked automatically:
    • Passing an object as a parameter (by value)
    • Returning an object from a function (by value)
    • Initializing a new object ```cpp #include “Cube.h” using Cube;

void foo(Cube cube) {}

int main() { Cube c; // trigger default constructor foo(c); // trigger copy constructor return 0; }

## Copy Assignment Operator
In C++, a copy assignment operator defines the behavior when an object is copied copied using the assignment operator =.
1. Copy Constructor vs. Assignment
  + A copy constructor creates a new object (constructor).
  + An assignment operator assigns a value to an existing object.
  + An assignment operator is always called on an object that has already been constructed.
2. Automatc Assignment operator
  + If we do not provide an assignment operator, the C++ compiler will provides an automatic assignment operator.
  + The automatic assignment operator will copy the contents of all member variables.
3. Custom Assignment Operator
  + A custom assignment operator:
    1. Is a public member function of the class.
    2. Has the function name operator=.
    3. Has a return value of a reference of the class' type.
    4. Has exactly one argument which ust be const reference of the class' type.
  + Eg. `Cube & Cube::operator=(const Cube & obj)`
namespace uiuc {
  // default constructor
  Cube::Cube() {
    length_ = 1
  // copy constructor
  Cube::Cube(const Cube & obj) {
    length_ = obj.length_;
  // assignment operator
  Cube & Cube::operator=(const Cube & obj) {
    length_ = obj.length_;
    return *this;
#include "Cube.h"
using uiuc::Cube;

int main() {
  Cube c;       // trigger default constructor
  Cube myCube;  // trigger default constructor
  myCube = c;   // trigger assignment operator
  return 0;

Variable Storage

In C++, an instance of a variable can be stored directly in memory, accessed by pointer, or accessed by reference.

Cube c;
Cube & r = c;
Cube * ptr = &c;
  1. Direct Storage
    • By default, variables are stored directly in memory.
    • The type of a variable has no modifiers.
    • The object takes up exactly its size in memory.
  2. Storage by Pointer
    • The type of a variable is modified with an asterisk (*).
    • A pointer takes a “memory address width” of memory, eg. 64 bits on a 64 bit system.
    • The pointer “points” to the allocated space of the object.
  3. Storage by Reference
    • A reference is an alias to existing memory and is denoted in the type with an ampersand (&).
    • A reference does not store memory itself, it is only an alias to another variable.
    • The alias must be assigned when the variable is initialized. ```cpp Cube c; int i;

Cube b; int j;

Cube &c; // illegal Cube &d = c; int &k = i;

4. Pass by / Return by
  + by value (default)
  + by pointer (modified with *)
  + by reference (modified with &, acts as an alias)
+ Never return a reference to a stack variable created on the stack of your current function.
## Class Destructor
+ When an instance of a class is cleaned up, the class destructor is the last call in a class's lifecycle.
1. Automatic Default Destructor
  + An automatic default destructor is added to your class if no other destructor is defined.
  + The only action of the automatic default destructor is to call the default destructor of all member objects.
  + An destructor should never be called directly. Instead, it is automatically called when the object's memory is being reclaimed by the system:
    + If the object is on the stack, when the function returns.
    + If the object is on the heap, when delete is used.
2. Custom Destructor
  + To add custom behaviro to the end-of-life of the function, a custom destructor can be defined as:
    + A custom destructor is a member function.
    + The function's destructor is the name of the class preceded by a tilde ~.
    + All destructors have zero arguments and no return type.
Cube::~Cube() {}

Template Types

  • A template type is a special type that can take on different types when the type is initialized.
  • Eg. std::vector uses a template type:
  • std::vector standard library class that provides the functionality of a dynamically growing array with a “templated” type.
    • Defined in: #include <vector>
    • Initialization: std::vector<T> v;
    • Add to (back) oof array: ::push_back(T);
    • Access specific element: ::operator[](unsigned pos);
    • Number of elements: ::size()
  • When initializing a “templated” type, the template type goes inside of <> at the end of the type name

    Templated Functions

  • A template variable is defined by declaring it before the beginning of a class or function:
    template <typename T>
    class List {
      // ...
        T data_;
template <typename T>
T max(T a, T b) {
  if (a > b) { return a; }
  return b;
  • Templated variables are checked at compile time, which allows for errors to be caught before running the program.


  • Inheritance allows for a class to inherit all member functions and data from a base class into a derived class.
  • Generic to Specialized: A base class is a generic form of a specialized, derived class. ```cpp class Shape { public: Shape(); Shape(double width); double getVolume() const; private: double width_; };

class Cube : public Shape { public: Cube(double width, HSLAPixel color); double getVolume() const; private: HSLAPixel color_; };

1. Initialization
  + When a derived class is instantiated, the derived class must construct the base class:
    + `Cube` must construct `Shape`
    + By default, uses default constructor
    + Custom constructor can be used with an `initialization list`
Cube::Cube(double width, HSLAPixel color) : Shape(width) {
  color_ = color;

double Cube::getVolume() const {
  return getWidth() * getWidth() * getWidth();
  1. Access Control
    • When a base class is inherited, the derived class:
    • Can access all public members of the base class
    • Can not access private members of the base class
  2. Initializer List
    • The syntax to initialize the base class is called the initializer list and can be used for several purposes:
    • Initialize a base class
    • Initialize the current class using another Constructor
    • Initialize the default values of member variables


      An array stores data in blocks of sequential memory.

      int values[10] = {2,3,5,7,11,13,15,17,21,23};
  3. Array Limitations:
  4. All data in an array must be of the same type + we can calculate the address of the nth element by adding index offset * sizeof type to the address of the first element.
  5. Arrays have a fixed capacity + array must be expanded(make a new larger array and copy over all the data) when reached capacity.
    int main() {
      int values[10] = { 2, 3, 5, 7, 11, 13, 15, 17, 21, 23 };
      std::cout << sizeof(int) << std::endl;
      int offset = (long)&(values[2]) - (long)&(values[0]);
      std::cout << offset << " should be twice of the number above" << std::endl;
      return 0;
  6. std::vector
    • Which implements an array that dynamically grows in size automatically. ```cpp int main() { std::vector cubes{ Cube(11), Cube(42), Cube(400) };

// Examine capacity:
std::cout « “Initial Capacity: “ « cubes.capacity() « std::endl; cubes.push_back( Cube(800) ); std::cout « “Size after adding: “ « cubes.size() « std::endl; std::cout « “Capacity after adding: “ « cubes.capacity() « std::endl;

// Using pointer arithmetic, ask the computer to calculate // the offset from the beginning of the array to [2]: int offset = (long)&(cubes[2]) - (long)&(cubes[0]); std::cout « “Memory separation: “ « offset « std::endl;

// Find a specific target cube in the array: Cube target = Cube(400); for (unsigned i = 0; i < cubes.size(); i++) { if (target == cubes[i]) { std::cout « “Found target at [” « i « ”]” « std::endl; } } return 0; }

## Linked Memory
Linked memory stores data together with a "link" to the location (in memory) of the next list node.
1. List Nodes: refers to pair of both the data and the link.
template <typename T>
class ListNode {
    T & data;
    ListNode *next;
    ListNode(T & data) : data(data), next(nullptr) {}
  1. Linked List: zero or more ListNode elements linked together form a Linked List.
    • A pointer called the “head pointer” stores the link to the begining of the list.
    • A pointer to NULL marks the end of the list. ```cpp template class List { public: const T & operator[](unsigned index); void insertAtFront(const T & data);

private: class ListNode { public: const T & data; ListNode *next; ListNode(const T & data) : data(data), next(nullptr) {} } ListNode *head_; }

3. Linked List:
  1. get: return element at index k
  2. insert: add an element to the list.
template <typename T>
const T & List<T>::operator[](unsigned index) {
  ListNode *node = head_;
  while (index > 0 && node->next != nullptr) {
    node = node->next;
  return node->data;

template <typename T>
void List<T>::insertAtFront(const T & data) {
  ListNode *node = new Listnode(data);
  node->next = head_;
  head_ = node;

Run-Time Analysis

  1. Array Resize: double each time
    • total work: O(N)
    • average work per element: O(1)
  2. Access nth element
    • Array: O(1) direct access via offset formula
    • LinkedList: O(N) traverse elements to reach the index
  3. Insert at front
    • Array: O(1) amortized constant when array size is doubled when copied
    • LinkedList: O(1) fixed constant by adding a new node
  4. Find data
    • Array: O(N)
    • LinkedList: O(N)
  5. Find data in sorted collection
    • Array: O(logN) using binary search
    • LinkedList: O(N)
  6. Insert after the given element
    • Array: O(N) require copying up to half of the array to make space for the new element
    • O(1): fixed constant by adding a new node
  7. Delete after the given element
    • Arrary: O(N) require copying up to half of the array to remove the blank space
    • LinkedList: O(1) fixed constant by set link to nullptr


      A queue is a first-in-first-out data structure.

  8. Abstract Data Type
    • A structure(like array, list)’s Abstract Data Type(ADT) is how data interacts with the structure
    • It is not an implementation, it is a description
  9. Queue ADT
    • create: create an empty queue
    • push: adds data to the back of the queue
    • pop: remove data from the front of the queue
    • empty: check if queue is empty Queue can be implemented with array or doubly linked list and get O(1) run time for all 4 operations


      A stack is a last-in-frist-out data structure

  10. Queue ADT
    • create: create an empty stack
    • push: adds data to the top of the stack
    • pop: remove data from the top of the queue
    • empty: check if stack is empty Stack can be implemented with array or singly linked list and get O(1) run time for all 4 operations

      Tree Terminology

      A tree is a linked structure with a sense of ancestry (parent, children, siblings, and more)

    • Each element in the tree is a node
    • Each connection between two nodes is an edge
    • Trees must always contain a root node that has no incoming edges
    • Nodes that contain no outgoing edges are called leaf nodes
    • In a tree, the nodes will store data and maybe labeled
    • Edges do not have names, but are referred to by the nodes they connect
    • Every node, except the root node, has exactly one parent node
    • A node’s children are the nodes with that node as it’s parent
    • Most ancestry terms apply as expected: sibling, ancestor, grandchildren, grandparent etc
    • To be a tree, three conditions must be true:
  11. Must have a root
  12. Must have directed edges
  13. Must not have a cycle
    • We say a tree is a “rooted, directed acyclic” structure

      Binary Tree

      A binary tree is a tree where every node has at most two children We will label every child as either left child or right child ```cpp // BinaryTree.h template class BinaryTree { public:

private: class TreeNode { public: T & data; TreeNode *left, *right; TreeNode(T & data) : data(data), left(nullptr), right(nullptr) {} }; TreeNode *root_; };

+ Binary Tree Property:
  1. height: number of edges in the longest path from root to leaf.
  2. full: a binary tree is full if and only if every node has either zero children or two children.
  3. perfect: a binary tree is perfect if and only if all interior nodes have two children and leaves are at the same level.
  4. complete: a binary tree is complete if and only if the tree is perfect up until the last level and all leaf nodes on the last level are pushed to the left.
## Binary Search Tree
A binary search tree (BST) is an ordered binary tree capable of being used as a search structure 
+ A binary tree is a BST if for every node in the tree:
  + Nodes in the left subtree are less than itself
  + Nodes in the right subtree are greater than itself
+ Dictionary ADT: a dictionary associates a key with data
  + find: finds the data associated with a key in the dictionary
  + insert: adds a key/data pair to the dictionary
  + remove: removes a key from the dictionary
  + empty: returns true if the dictionary is empty
+ BST-based Dictionary:
  + Use BST to implement a dictionary will store both a key and data at every node
+ BST::remove
  + Zero children: simple, delete the node
  + One child: simple works like a linked list
  + Two children:
    1. Find the in-order-predecessor (IOP) of the node to be removed. - the largest node < node
    2. Swap with the IOP
    3. Remove the node in it's new position
template <typename K, typename D>
class Dictionary {
    const D & find(const K & key);
    void insert(const K & key, const D & data);
    const D & remove(const K & key);

    class TreeNode {
        const K & key;
        const D & data;
        TreeNode *left, *right;
        TreeNode(const K & key, const D & data)
          : key(key), data(data), left(nullptr), right(nullptr) {}

  TreeNode *head_;

template <typename K, typename D>
typename Dictionary<K, D>::TreeNode *& Dictionary<K, D>::_find(
  const K & key, TreeNode *& cur) const {
    if (cur == nullptr) { return cur; }
    else if (cur->key == key) { return cur; }
    else if (cur->key > key) { return _find(key, cur->left); }
    else { return _find(key, cur->right); }

template <typename K, typename D>
const D & Dictionary<K, D>::find(const K & key) {
  TreeNode *& node = _find(key, head_); // *& is a reference / alias to the pointer
  if (node == nullptr) { throw std::runtime_error("key not found"); }
  return node->data;

template <typename K, typename D>
void Dictionary<K, D>::insert(const K & key, const D & data) {
  TreeNode *& node = _find(key, head_);
  node = new TreeNode(key, data);

template <typename K, typename D>
const D & Dictionary<K, D>::remove(const K & key) {
  TreeNode *& node = _find(key, head_);
  return _remove(node);

template <typename K, typename D>
const D & Dictionary<K, D>::_remove(TreeNode *& node) {
  if (node->left == nullptr && node->right == nullptr) {
    const D & data = node->data;
    node = nullptr;
    return data;
  if (node->left != nullptr && node->right == nullptr) {
    const D & data = node->data;
    TreeNode *temp = node;
    node = node->left;
    return data;
  if (node->left == nullptr && node->right != nullptr) {
    const D & data = node->data;
    TreeNode *temp = node;
    node = node->right;
    return data;
  TreeNode *& iop = _iop( node->left );
  _swap( node, iop );
  return _remove( node );

BST analysis

  1. There are n! different ways to create BSTs with the same data
    • The worst-case BST will have a height proportional to the number of nodes
    • An average BST will have a height proportional to the logarithm of the number of nodes
  2. Using a height balance factor, we can formalize if a given BST is balanced
    • height balance factor of a node is the difference in height between its two subtrees
    • A balanced BST is a BST where every node’s balance factor has a magnitude of 0 or 1

      Balanced BST

      Balanced BSTs are height-balanced trees that ensures nearly half of the data is located in each subtree

    • BST Rotation Summary | rotation | balance factor of the lowest point of imbalance | balance factor of the node in the direction of imbalance | |———————|————————————————-|———————————————————-| | left rotation | 2 | 1 | | right rotation | -2 | -1 | | right-left rotation | 2 | -1 | | left-right rotation | -2 | 1 |
    • BST rotations restore the balance property to a tree after an insert causes a BST to be out of balance
      • rotations are local operations
      • rotations do not impact the broader tree
      • rotations run in O(1) time
    • These trees are called “AVL Trees”

      AVL (Adelson-Velsky and Landis) Analysis

      AVL Trees is an implementation of a balanced BST

      • It starts with a BST implementation and adds two key ideas:
    1. Maintains the height at each node
    2. Maintains the balance factor after insert and remove
      • Everything about finding, inserting, and removing from a BST remains true.
      • In an AVL tree, we add steps to ensure we maintain balance
        • Extra work on insert/remove
        • To quickly compute the balance factor, AVL trees store the height of every node as part of the node itself
      • Insert
  3. Insert at proper place
  4. check for imbalance
  5. Rotate, if necessary
  6. Update height ```cpp template <typename K, typename D> void AVL<K, D>::_ensureBalance(TreeNode *& cur) { int balance = height(cur->right) - height(cur->left); if ( balance == -2 ) { int l_balance = height(cur->left->right) - height(cur->left->left); if ( l_balance == -1 ) _rotateRight( cur ); else _rotateLeftRight( cur ); } else if (balance == 2) { int r_balance = height(cur->right->right) - height(cur->right->left); if ( r_balance == 1 ) _rotateLeft( cur ); else _rotateRightLeft( cur );
    } _updateHeight(cur); }

template <typename K, typename D> void AVL<K, D>::_updateHeight(TreeNode *& cur) { cur->height = 1 + max(height(cur->left), height(cur->right)); }

template <typename K, typename D> void AVL<K, D>::_rotateLeft(TreeNode *& cur) { TreeNode *x = cur; TreeNode *y = cur->right;

x->right = y->left; y->left = x; cur = y;

_updateHeight(x); _updateHeight(y); }

template <typename K, typename D>
const D & AVL<K, D>::_iopRemove(TreeNode *& node, TreeNode *& iop) {
  if (iop->right != nullptr) {
    const D & d = _iopRemove(node, iop->right);
    if (iop) _ensureBalance(iop); 
    else return d;
  _swap(node, iop);
  std::swap(node, iop);

  return _remove(iop);


Each tree node contains multiple keys: order m

  • For a B-tree “of order m”
    1. All keys within a node are in sorted order
    2. Each node contains no more than m-1 keys
    3. Each internal node can have at most m children, so a B-tree of order m is like an m-way tree
    4. Each internal node has exactly one more child than key
      • A root node can be a leaf or have [2, m] children
      • Each non-root, internal node has [ceil(m/2), m] children
    5. All leaves are on the same level