Count nodes in a BST that lies within a given range
Given a BST, count the total number of nodes that lie within a given range.
Tag: Depth-first search
Check whether a directed graph is Eulerian
An Eulerian trail (or Eulerian path) is a path in a graph that visits every edge exactly once. Given a directed graph, check whether it has an Eulerian path or not.
Check if removing an edge can split a binary tree into two equal size trees
Given a binary tree, check if removing an edge can split it into two binary trees of equal size.
In-place merge two height-balanced BSTs
Given two height-balanced binary search trees, in-place merge them into a single balanced binary search tree. For each node of a height-balanced tree, the difference between its left and right subtree height is at most 1.
Determine whether two nodes lie on the same path in a binary tree
Given a binary tree and two tree pointers, x and y, write an efficient algorithm to check if they lie on the same root-to-leaf path in the binary tree. In other words, determine whether x is an ancestor of y, or x is a descendant of y.
Print all pairs of anagrams in a set of strings
Given a set of strings, print all pairs of anagrams together. Two strings, X and Y, are called anagrams if we can get a string Y by rearranging the letters of the string X and using all the characters of the string X exactly once.
Check if a set of words can be rearranged to form a circle
Given a set of words, check if the individual words can be rearranged to form a circle. Two words, X and Y, can be put together in a circle if the last character of X is the same as the first character of Y or vice-versa.
Find root vertex of a graph
A root vertex of a directed graph is a vertex u with a directed path from u to v for every pair of vertices (u, v) in the graph. In other words, all other vertices in the graph can be reached from the root vertex.
Evaluate a Binary Expression Tree
Evaluate a given binary expression tree representing algebraic expressions. A binary expression tree is a binary tree, where the operators are stored in the tree’s internal nodes, and the leaves contain constants.
Check if each node of a binary tree has exactly one child
Given a binary tree, check if each node has exactly one child or not. In other words, check whether the binary tree is skewed or not.
Perform boundary traversal on a binary tree
Given a binary tree, perform the boundary traversal of it. The solution should print the boundary nodes starting from the root of the tree, in an anti-clockwise direction, without any duplicates.
Eulerian cycle in directed graphs
Given a directed graph, check if it is possible to construct a cycle that visits each edge exactly once, i.e., check whether the graph has an Eulerian cycle or not.