Check if a binary tree is a min-heap or not
Given a binary tree, check if it is a min-heap or not. In order words, the binary tree must be a complete binary tree where each node has a higher value than its parent’s value.
Category: Binary Tree
Construct a binary tree from inorder and preorder traversal
Write an efficient algorithm to construct a binary tree from the given inorder and preorder sequence.
Find the size of the largest BST in a binary tree
Given a binary tree, find the size of the largest BST (Binary Search Tree) in it.
Determine if a binary tree satisfies the height-balanced property of a red–black tree
Write an efficient algorithm to determine if a binary tree satisfies the height-balanced property of the red–black tree or not.
Construct a full binary tree from the preorder sequence with leaf node information
Write an efficient algorithm to construct a full binary tree from a sequence of keys representing preorder traversal and a boolean array that determines if the corresponding key in the preorder traversal is a leaf node or an internal node.
Convert a ternary tree to a doubly-linked list
Write an efficient algorithm to convert a ternary tree into a doubly-linked list. A ternary tree is a tree data structure in which each node has three child nodes distinguished as left, mid, and right.
Construct a full binary tree from a preorder and postorder sequence
A full binary tree is a tree in which every node has either 0 or 2 children. Write an efficient algorithm to construct a full binary tree from a given preorder and postorder sequence.
Depth-First Search (DFS) vs Breadth-First Search (BFS)
This post will cover the difference between the Depth–first search (DFS) and Breadth–first search (BFS) algorithm used to traverse/search tree or graph data structure.
Find all possible binary trees having the same inorder traversal
Given an inorder sequence of a binary tree, find all possible binary trees having that same inorder traversal.
Construct a Cartesian tree from an inorder traversal
Write an efficient algorithm to construct a Cartesian tree from inorder traversal. A Cartesian tree is a binary tree with the heap property: the parent of any node has a smaller value than the node itself.
Set next pointer to the inorder successor of all nodes in a binary tree
Given a binary tree where each node has one extra pointer next, set it to the inorder successor for all binary tree nodes.
Efficiently print all nodes between two given levels in a binary tree
Given a binary tree, efficiently print all nodes between two given levels in a binary tree. The nodes for any level should be printed from left to right.