InterviewCoding

Trees

Trees

100 questions on binary trees and binary search trees — traversals, construction, and structural problems.

Get All Root-to-Leaf Paths

Return every root-to-leaf path in a binary tree as a list of node values, instead of an arrow-joined string.

Binary Tree Basics

An introduction to the Node and BinTree building blocks used throughout the Binary Trees series, plus a sample tree these exercises build on.

Binary Tree Paths

Return every root-to-leaf path in a binary tree as an arrow-joined string.

Binary Tree Traversals: Preorder, Inorder, Postorder

Add preorder, inorder, and postorder traversal methods to BinTree and see how each visits the same sample tree in a different order.

Convert a Sorted Array to a Balanced BST

Build a height-balanced binary search tree from an array sorted in ascending order.

Invert Binary Tree

Flip a binary tree into its mirror image by swapping every node's left and right children.

Minimum Absolute Difference in a BST

Find the smallest absolute difference between the values of any two distinct nodes in a binary search tree.

Range Sum of a BST

Sum every node value in a binary search tree that falls within a given inclusive range.

Search in a Binary Search Tree

Find the node with a given value in a binary search tree and return the subtree rooted there.

Symmetric Tree

Determine whether a binary tree is a mirror of itself around its center.

Binary Tree Left Side View

Return the value of the leftmost node visible at each level of a binary tree, from top to bottom.

Print Left View of a Binary Tree

Print the first node visible at each level of the sample tree, extending level order traversal with a single boolean flag.

Binary Tree Level Order Traversal

Add a queue-based level order (breadth-first) traversal to BinTree, visiting the sample tree one level at a time.

Count Nodes With the Highest Score

There is a binary tree rooted at 0 consisting of n nodes.

Count Pairs of Connectable Servers in a Weighted Tree Network

You are given an unrooted weighted tree with n vertices representing servers numbered from 0 to n - 1, an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional...

Count the Number of Good Nodes

There is an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0.

Delete a Node in a Binary Search Tree

Remove the node with a given value from a binary search tree while preserving its ordering property.

Diameter of Binary Tree

Find the length, in edges, of the longest path between any two nodes in a binary tree.

Find Subtree Sizes After Changes

You are given a tree rooted at node 0 that consists of n nodes numbered from 0 to n - 1.

Insert into a Binary Search Tree

Insert a new value into a binary search tree while preserving its ordering property.

Kth Smallest Element in a BST

Find the k-th smallest value stored in a binary search tree.

Lowest Common Ancestor in a BST

Find the lowest common ancestor of two given values in a binary search tree, using the tree's ordering to avoid a generic tree search.

Make Costs of Paths Equal in a Binary Tree

You are given an integer n representing the number of nodes in a perfect binary tree consisting of nodes numbered from 1 to n.

Maximize the Number of Target Nodes After Connecting Trees I

There exist two undirected trees with n and m nodes, with distinct labels in ranges [0, n - 1] and [0, m - 1], respectively.

Maximum Score After Applying Operations on a Tree

There is an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0.

Minimum Fuel Cost to Report to the Capital

There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads.

Minimum Increments to Equalize Leaf Paths

You are given an integer n and an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1.

Minimum Time to Collect All Apples in a Tree

Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices.

Most Profitable Path in a Tree

There is an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0.

Number of Nodes in the Sub-Tree With the Same Label

You are given a tree (i.e.

Number of Ways to Assign Edge Weights I

There is an undirected tree with n nodes labeled from 1 to n, rooted at node 1.

Path In Zigzag Labelled Binary Tree

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

Reachable Nodes With Restrictions

There is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

Time Needed to Inform All Employees

A company has n employees with a unique ID for each employee from 0 to n - 1.

Unique Binary Search Trees

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

Validate a Binary Search Tree

Determine whether a binary tree satisfies the binary search tree property at every node, not just between direct parent-child pairs.

Validate Binary Tree Nodes

You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one...

Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use preorder traversal.

Check if DFS Strings Are Palindromes

You are given a tree rooted at node 0, consisting of n nodes numbered from 0 to n - 1.

Collect Coins in a Tree

There exists an undirected and unrooted tree with n nodes indexed from 0 to n - 1.

Count Number of Possible Root Nodes

Alice has an undirected tree with n nodes labeled from 0 to n - 1.

Count Paths That Can Form a Palindrome in a Tree

You are given a tree (i.e.

Count Subtrees With Max Distance Between Cities

There are n cities numbered from 1 to n.

Count Valid Paths in a Tree

There is an undirected tree with n nodes labeled from 1 to n.

Count Ways to Build Rooms in an Ant Colony

You are an ant tasked with adding n new rooms numbered 0 to n-1 to your colony.

Create Components With Same Value

There is an undirected tree with n nodes labeled from 0 to n - 1.

Cycle Length Queries in a Tree

You are given an integer n.

Difference Between Maximum and Minimum Price Sum

There exists an undirected and initially unrooted tree with n nodes indexed from 0 to n - 1.

Find Minimum Diameter After Merging Two Trees

There exist two undirected trees with n and m nodes, numbered from 0 to n - 1 and from 0 to m - 1, respectively.

Find Number of Coins to Place in Tree Nodes

You are given an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0.

Find the Maximum Sum of Node Values

There exists an undirected tree with n nodes numbered 0 to n - 1.

Find Weighted Median Node in Tree

You are given an integer n and an undirected, weighted tree rooted at node 0 with n nodes numbered from 0 to n - 1.

Frog Position After T Seconds

Given an undirected tree consisting of n vertices numbered from 1 to n.

Kth Smallest Path XOR Sum

You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1.

Longest Path With Different Adjacent Characters

You are given a tree (i.e.

Longest Special Path

You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1, represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi, lengthi]...

Longest Special Path II

You are given an undirected tree rooted at node 0, with n nodes numbered from 0 to n - 1.

Maximize Sum of Weights after Edge Removals

There exists an undirected tree with n nodes numbered 0 to n - 1.

Maximize the Number of Target Nodes After Connecting Trees II

There exist two undirected trees with n and m nodes, labeled from [0, n - 1] and [0, m - 1], respectively.

Maximum Good Subtree Score

You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1.

Maximum Number of K-Divisible Components

There is an undirected tree with n nodes labeled from 0 to n - 1.

Maximum Points After Collecting Coins From All Nodes

There exists an undirected tree rooted at node 0 with n nodes labeled from 0 to n - 1.

Maximum Profit from Trading Stocks with Discounts

You are given an integer n, representing the number of employees in a company.

Minimize the Total Price of the Trips

There exists an undirected and unrooted tree with n nodes indexed from 0 to n - 1.

Minimum Edge Weight Equilibrium Queries in a Tree

There is an undirected tree with n nodes labeled from 0 to n - 1.

Minimum Score After Removals on a Tree

There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

Minimum Weighted Subgraph With the Required Paths II

You are given an undirected weighted tree with n nodes, numbered from 0 to n - 1.

Number of Good Paths

There is a tree (i.e.

Number of Ways to Assign Edge Weights II

There is an undirected tree with n nodes labeled from 1 to n, rooted at node 1.

Number Of Ways To Reconstruct A Tree

You are given an array pairs, where pairs[i] = [xi, yi], and: Let ways be the number of rooted trees that satisfy the following conditions: Two ways are considered to be different...

Number of Ways to Reorder Array to Get Same BST

Given an array nums that represents a permutation of integers from 1 to n.

Shortest Path in a Weighted Tree

You are given an integer n and an undirected, weighted tree rooted at node 1 with n nodes numbered from 1 to n.

Smallest Missing Genetic Value in Each Subtree

There is a family tree rooted at 0 consisting of n nodes numbered 0 to n - 1.

Subtree Inversion Sum

You are given an undirected tree rooted at node 0, with n nodes numbered from 0 to n - 1.

Sum of Distances in Tree

There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

Time Taken to Mark All Nodes

There exists an undirected tree with n nodes numbered 0 to n - 1.

Tree of Coprimes

There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges.