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.
Tag: Depth-first search
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).
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.
Find correct order of alphabets in a given dictionary of ancient origin
Given a dictionary of ancient origin where the words are arranged alphabetically, find the correct order of alphabets in the ancient language.
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.
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.