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.
Tag: Recursive
Add a single-digit number to a linked list representing a number
Given a singly linked list whose nodes represent digits of a number, add a single-digit number to it.
Find all Possible Topological Orderings of a DAG
Given a Directed Acyclic Graph (DAG), print all its topological orderings. A Topological ordering of a directed graph G is a linear ordering of the nodes as v1, v2,…,vn such that all edges point forward: for every edge (vi, vj), we have i < j.
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.
Reverse every alternate group of `k` nodes in a linked list
Given a linked list, reverse every alternate group of k nodes where k is a given positive integer.
Implement a stack using the queue data structure
This post will implement a stack using the queue data structure. In other words, design a stack that supports push and pop operations using standard enqueue and dequeue operations of the queue.
Determine whether a linked list is palindrome or not
Given a singly linked list of integers, determine if the linked list is a palindrome 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.
Sort a doubly-linked list using merge sort
Given a doubly linked list, sort it using the merge sort algorithm. Merge sort is an efficient sorting algorithm that uses the divide-and-conquer technique to sort a sequence of items.
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.
Find total ways to reach n’th stair with at-most `m` steps
Given a staircase, find the total number of ways to reach the n’th stair from the bottom of the stair when a person is only allowed to take at most m steps at a time.