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.
Category: Tree
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.
Check if a given sequence represents the preorder traversal of a BST
Given a distinct sequence of keys, check if it can represent a preorder traversal of a binary search tree (BST).
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.
Count subtrees in a BST whose nodes lie within a given range
Given a BST, count subtrees in it whose nodes lie within a given range.
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.
Build a Binary Search Tree from a postorder sequence
Given a distinct sequence of keys representing the postorder traversal of a binary search tree, construct a BST from it.
Build a Binary Search Tree from a preorder sequence
Given a distinct sequence of keys representing the preorder sequence of a binary search tree (BST), construct a BST from it.