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.
Tag: Recursive
Fix children-sum property in a binary tree
Write an efficient algorithm to fix the children-sum property in a given binary tree. The only operation allowed is an increment operation on the node’s value.
Find the shortest unique prefix for every word in an array
Given an array of words where no word is the prefix of another, find the shortest unique prefix to identify each word in the array uniquely.
Check whether the leaf traversal of given binary trees is the same or not
Given two binary trees, check whether the leaf traversals of both trees are the same or not.
Construction of an expression tree
Construct an expression tree from a given postfix notation and print the infix notation. The binary expression tree is a binary tree whose leaves are operands, such as constants or variable names, and the other nodes contain operators.
Extract leaves of a binary tree into a doubly-linked list
Given a binary tree, extract all its leaves into a doubly-linked list, i.e., remove all leaf nodes from the binary tree and construct a doubly linked list out of them.
Maximum path sum in a binary tree
Given a binary tree, write an efficient algorithm to find the maximum path sum between any two nodes in it. The path can start and end at any node in the tree and need not go through the root.
Print complete Binary Search Tree (BST) in increasing order
Given a level order representation of a complete binary search tree, print its elements in increasing order.
Find the minimum depth of a binary tree
Given a binary tree, find its minimum depth. The minimum depth is the total number of nodes along the shortest path from the root node down to the nearest leaf node.
Minimum-weight triangulation of a convex polygon
A triangulation of a convex polygon results in a set of non-intersecting diagonals between non-adjacent vertices, which completely partition the interior of the convex hull of the polygon into triangles.
Find maximum profit that can be earned by conditionally selling stocks
Given a list containing future price predictions of two different stocks for the next n–days, find the maximum profit earned by selling the stocks with a constraint that the second stock can be sold, only if no transaction happened on the previous day for any of the stock.
Check whether an undirected graph is Eulerian
Given an undirected graph, check whether it has an Eulerian path or not. In other words, check if it is possible to construct a path that visits each edge exactly once.