Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structure
binary tree

What is a Binary Tree?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Trees are one of the most fundamental data structures. They are used to store and organize data.

A binary tree is a tree data structure composed of nodes, each of which has at most, two children, referred to as left and right nodes. The tree starts off with a single node known as the root.

Each node in the tree contains the following:

  1. Data
  2. Pointer to the left child
  3. Pointer to the right child

In case of a leaf node, the pointers to the left and right child point to null.

svg viewer

Note: There is no specific way to arrange data in a binary tree.

Common operations

Following is a list of common operations that can be performed on a binary tree:

1. Insertion

Elements may be inserted into a binary tree in any order. The very first insertion operation creates the root node. Each insertion that follows iteratively searches for an empty location at each level of the tree.

Upon finding an empty left or right child, the new element is inserted. By convention, the insertion always begins from the left child node.

svg viewer

2. Deletion

An element may also be removed from the binary tree. Since there is no particular order among the elements, upon deletion of a particular node, it is replaced with the right-most element.

Let’s look at an example to get a better idea of how the deletion process works.

svg viewer

Binary trees are one of the most efficient and frequently used data structures. They represent structural relationships in data and are used to represent hierarchies.

3. Tree traversal

Another frequently used tree operation is traversal. Tree traversal is the process of visiting each node present in a tree. There are three methods of tree traversal:

  1. In-order traversal
  2. Post-order traversal
  3. Pre-order traversal

RELATED TAGS

data structure
binary tree
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring