Marcy Blog

Failed to be a geek

Problem: Diameter of Binary Tree

Question Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path...

Problem: Binary Tree Maximum Path Sum

Question Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-ch...

Problem: Recover Binary Search Tree

Question Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Solution For a binary search tree, we know if we print the nodes via...

Problem: Validate Binary Search Tree

Question Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node...

Problem: kth Smallest in a Binary Search Tree

Question Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements. Follow up: What if...

Problem: Insert into a BST

Question Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guara...

Problem: Binary Tree Right Side View

Question Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. For example: Given the following binary tre...

Problem: Maximum Depth of Binary Tree

Question Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. For example: Given binary...

Problem: Binary Tree Min Depth

Question 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. Solution 1 Traverse the ...

Problem: LRU Cache

Question Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) ...