Traversal

Lowest Common Ancestor of a Binary Tree

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 ...

Binary Tree Inorder Traversal

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 ...

Binary Tree Postorder Traversal

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 ...

Generate Parentheses Problem

Problem Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses. OR Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Follow up Make sure the returned list of strings are sorted. Examples Example 1: Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] ...

Inorder Successor in Binary Search Tree

Problem Given a Binary Search tree, find the inorder successor of a node. Definition See the definition here. Examples Example 1: 10 / \ 5 30 / \ 22 35 ...

Inorder Successor in Binary Search Tree Using Parent link

Problem Given a node in a binary search tree, return the next bigger element, also known as the inorder successor. You can assume each node has a parent pointer. Definition See the definition here. Here is gist though: The in-order successor of a node in a BST is the next node in in-order traversal, which, for a given node, is the node with the smallest value larger than the given node’s value. ...

Kth largest element in Binary Search Tree

Problem Given a Binary Search Tree (BST) and a positive integer k, find the k’th largest element in the Binary Search Tree. Examples Example 1: Input: 2 / \ 1 3 and k = 2 Return : 2 As 2 is the second smallest element in the tree. ...

Construct Binary Tree from Inorder and Level Order Traversal

Problem Given a inorder and level order traversal, construct a binary tree from that. Examples Example 1: 3 / \ 9 20 / \ 15 7 ...

Convert Sorted Array to height-balanced Binary Search Tree

Problem Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. Examples Example 1: Input: nums = [1, 2, 3, 4, 5, 6] Output: [3,2,5,1,null,4,6] Explanation: [4,2,5,1,3,null,6] is also accepted. ...

Evaluation of Arithmetic Expression Tree

Problem Given a simple expression tree, consisting of basic binary operators i.e., + , – , * and / and some integers, evaluate the expression tree. Examples Example 1: graph TD; A(+) --- B(*) & C("-") B --- D(5) & E(4) C --- F(100) & G(20) Input: root = ["+", "*", "-", "5", "4", "100", "20"] Output: 100 ...