Search⌘ K
Home
Courses
Data Structures for Coding Interviews in C++

What is a Binary Tree?

Discover the fundamentals of binary trees, including definitions and different types such as complete, full, and perfect binary trees. Understand their structures, properties, and how to calculate the number of nodes for each type from a coding perspective in C++.

We'll cover the following...

Introduction

A tree in which each node can have a maximum of two children is known as a binary tree. We can refer to these children as the left and the right child. The figure below shows what a Binary Tree looks like :

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

Types of Binary Trees

Complete Binary Trees

A complete binary tree is a binary tree in which all the levels of the tree are fully filled, except for perhaps the last level, which can be filled from left to right. The total number of nodes in a complete binary tree can be expressed as:

2h≤total number of nodes≤2(h+1)−12^{h} \leq \text{total number of nodes} \leq 2^{(h+1)}-1 ...