Hello Interview | Data Structures and Algorithms

Limited Time Offer:30% off Hello Interview Premium 🎉

30% off Hello Interview Premium 🎉

Main

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Practice

Learn

System Design

ML System Design

DSA

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Discord

Refer a Friend

Pricing

Become a Coach

Pricing Become a Coach

Get Premium

Binary Trees

A binary tree is a tree data structure in which each node has at most two children, referred to the left and right child of the node. This page covers properties of binary trees and common algorithms that can be applied to binary trees for the coding interview.

Properties of Binary Trees

The top node of a binary tree is called the root. Each node in a binary tree can have at most two children, referred to as the left child and right child. A node that does not have any children is called a leaf node:

Height of a Binary Tree The height of a binary tree is the number of edges on the longest path between the root node and a leaf node. This is also known as the depth of the tree.

Balanced Binary Tree A binary tree is balanced if the height of the left and right subtrees of every node differ by at most 1.

A balanced binary tree.

An unbalanced binary tree.

Complete Binary Tree A binary tree is complete if every level, except possibly the last, is completely filled, and all nodes are as far left as possible. Complete binary trees are an important concept in heap data structures.

A complete binary tree.

A complete binary tree has a height of O(log(n)), where n is the number of nodes in the tree.

Binary Search Tree A binary search tree (BST) is a binary tree where:

All nodes in the left subtree of the root have a value less than the root.
All nodes in the right subtree of the root have a value greater than the root.

The same property applies to all subtrees in the tree. This property allows for efficient search, insertion, and deletion of nodes in the tree.

A binary search tree. All nodes in the left subtree are less than 4, while all nodes in the right subtree are greater than 4.

Pre-Order Traversal

In a pre-order traversal, the root node is visited first, followed by the left subtree, and then the right subtree. The same order is repeated for each subtree. This corresponds to the order in which nodes are added to the call stack during a recursive traversal.

Pre-order traversals are useful for copying a tree, as the order of nodes is preserved.

The order in which the nodes are visited are labeled next to each node.

Animated Pre-Order Traversal


def preOrderTraversal(root):
    if root is None:
        return

    print(root.val)
    preOrderTraversal(root.left)
    preOrderTraversal(root.right)

pre-order traversal

0 / 52

In-Order Traversal

In an In-Order traversal, the left subtree is visited first, followed by the root node, and then the right subtree.

In-Order Traversal on a Binary Search Tree (BST)

Note that an In-order traversal on a binary search tree (BST) like the one shown below will give you the nodes in sorted order.

The order in which the nodes are visited are labeled next to each node.

Animated In-Order Traversal


def inOrderTraversal(root):
    if root is None:
        return

    inOrderTraversal(root.left)
    print(root.val)
    inOrderTraversal(root.right)

in-order traversal

0 / 52

Post-Order Traversal

In a post-order traversal, the left subtree is visited first, followed by the right subtree, and then the root node. This corresponds to the order in which nodes are popped off the call stack during a recursive traversal.

A post-order traversal is useful for deleting nodes from a tree, as it ensures that a parent node is deleted after its children.

The order in which the nodes are visited are labeled next to each node.

Animated Post-Order Traversal


def postOrderTraversal(root):
    if root is None:
        return

    postOrderTraversal(root.left)
    postOrderTraversal(root.right)
    print(root.val)

post-order traversal

0 / 52

Summary

Traversal	Order	Notes
Pre-Order	Root, Left, Right	Root before children
In-Order	Left, Root, Right	In-Order on a BST gives nodes in sorted order
Post-Order	Left, Right, Root	Children before root

Next: Overview

Your account is free and you can post anonymously if you choose.

Binary Trees

Properties of Binary Trees

Pre-Order Traversal

In-Order Traversal

Post-Order Traversal

Summary

Questions

Learn

Links

Legal

Contact