Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in Python

What is a Binary Tree?

Explore the concept of binary trees in this lesson, including their definition and various types such as complete, full, and perfect binary trees. Understand the properties and structure of each type to build a solid foundation for data structures used in programming and coding interviews.

We'll cover the following...

Introduction

A binary tree is a tree in which each node has between 0-2 children. They’re called the left and right children of the node. 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.

%0 node_1 1 node_1544167982032 1 node_1->node_1544167982032 node_3 5 node_1->node_3 node_1544167947483 10 node_3->node_1544167947483 node_1544167929828 3 node_3->node_1544167929828
Not a complete Binary Tree
%0 node_1 1 node_2 2 node_1->node_2 node_3 3 node_1->node_3 node_1544168219085 2 node_2->node_1544168219085 node_1544168233742 2 node_2->node_1544168233742 node_1544168288100 3 node_3->node_1544168288100
A Complete Binary Tree

Full Binary Trees

  • In a full or ‘proper’ binary tree, every node has 0 or 2 children. No node can have 1 child.
  • The total number of nodes in a full binary tree of height ‘h’ can be expressed as:

2h+1≤2h + 1 \leq ...