Problem Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it. Note: A subtree must include all of its descendants. Examples Example 1: 10 / \ [5] 15 / \ \ [1] [8] 7 ...
Minimum Height Trees Problem A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree. Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs). ...
Problem Given the root of a binary tree, return the length of the longest consecutive sequence path. A consecutive sequence path is a path where the values increase by one along the path. Note that the path can start at any node in the tree, and you cannot go from a node to its parent in the path. Solution Method 1 - Using BFS Here is the approach: ...
Minimum Depth of Binary Tree Problem Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Examples Example 1: graph TD; 3 --- 9 & 20; 20 --- 15 & 7; ...
Count Number of Leaf Nodes in Binary Tree Problem Count leaf nodes in a binary tree Examples Example 1: 3 / \ 9 20 / \ 15 7 Input: root = [3,9,20,null,null,15,7] Output: 2 ...
Problem Given the root of a complete binary tree, return the number of the nodes in the tree. Definition and Properties of Complete Binary Tree Complete Binary Tree Examples Example 1: 1 / \ 2 3 / \ / 4 5 6 ...
Problem Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. Definition Lowest Common Ancestor Definition Examples Example 1: graph TD; 6; 6 --- 2; 6 --- 8; 2 --- 0; 2 --- 4; 8 --- 7; 8 --- 9; 4 --- 3; 4 --- 5; style 2 fill:#FF9933 style 8 fill:#FF9933 style 6 fill:#3399FF ...
Problem Given a binary tree, write a non recursive or iterative algorithm for Inorder traversal. Inorder Traversal First, visit all the nodes in the left subtree Then the root node Visit all the nodes in the right subtree inorder(root->left) display(root->data) inorder(root->right) Example Example 1: 1 \ 2 / 3 ...
Problem Given a binary tree, write an algorithm for postorder traversal. Postorder Traversal Visit all the nodes in the left subtree Visit all the nodes in the right subtree Visit the root node postorder(root->left) postorder(root->right) display(root->data) Examples Example 1: 1 \ 2 / 3 ...
Problem Given a binary tree, write a program to count the number of Single Valued Subtrees. A Single Valued Subtree is one in which all the nodes have same value. Expected time complexity is O(n). Example Examples 1: 5 / \ 1 5 / \ \ 5 5 5 ...