Deletion from BST (Binary Search Tree)
Deletion from BST – write an efficient function to delete a given key in BST. To delete a node from BST, there are three possible cases to consider.
Tag: Recursive
Search a given key in BST – Iterative and Recursive Solution
Given a BST, write an efficient function to search a given key in it. The algorithm should return the parent node of the key and print if the key is the left or right node of the parent node. If the key is not present in the BST, the algorithm should be able to determine that.
Insertion in a BST – Iterative and Recursive Solution
A Binary Search Tree (BST) is a rooted binary tree, whose nodes each store a key (and optionally, an associated value), and each has two distinguished subtrees, commonly denoted left and right.
Find maximum sum root to leaf path in a binary tree
Given a binary tree, write an efficient algorithm to find the maximum sum root-to-leaf path, i.e., the maximum sum path from the root node to any leaf node in it.
Truncate a binary tree to remove nodes that lie on a path having a sum less than `k`
Given a binary tree and a number k, remove nodes from the tree which lie on a complete path having a sum less than k.
Convert a binary tree to a full tree by removing half nodes
Given a binary tree, convert it into a full tree by removing half nodes (remove nodes having one child).
Sink nodes containing zero to the bottom of a binary tree
Given a binary tree containing many zero nodes, sink nodes having zero value at the bottom of the subtree rooted at that node. In other words, the output binary tree should not contain any node having zero value that is the parent of the node having a non-zero value.
In-place convert a binary tree to a doubly-linked list
Given a binary tree, in-place convert it into a doubly linked list. The left and right pointers of binary tree nodes should act as previous and next pointers in a doubly-linked list, and the doubly linked list nodes should follow the same order of nodes as inorder traversal on the tree.
Print diagonal traversal of a binary tree
Given a binary tree, print all nodes for each diagonal having negative slope (\). Assume that the left and right child of a node makes a 45–degree angle with the parent.
Perform vertical traversal of a binary tree
Given a binary tree, perform vertical traversal on it. In vertical traversal, nodes of a binary tree are printed in vertical order. Assume that the left and right child makes a 45–degree angle with the parent.
Find the vertical sum of a binary tree
Given a binary tree, the print vertical sum of it. Assume the left and right child of a node makes a 45–degree angle with the parent.
Find distance between given pairs of nodes in a binary tree
Given a binary tree, determine the distance between given pairs of nodes in it. The distance between two nodes is defined as the total number of edges in the shortest path from one node and another.