Construct Binary Search Tree From Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal. (Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.) Example 1 Input: [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12] Note: 1 <= preorder.

by lek tin in "algorithm" access_time 2-min read

Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node p is the node with the smallest key greater than p.val. Example 1 Input: root = [2,1,3], p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type. Example 2 Input: root = [5,3,6,2,4,null,null,1], p = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null.

by lek tin in "algorithm" access_time 2-min read

Two Sum Iv Input Is a Bst

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target. Example 1 Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True Example 2 Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False Solution # time: `O(n)` # space: `O(n)` # Definition for a binary tree node.

by lek tin in "algorithm" access_time 2-min read

Serialize and Deserialize BST

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

by lek tin in "algorithm" access_time 2-min read

Convert Binary Search Tree to Sorted Doubly Linked List

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Let’s take the following BST as an example, it may help you understand the problem better: We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

by lek tin in "algorithm" access_time 2-min read

Validate Binary Search Tree

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’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees. Example 1 Input: 2 / \ 1 3 Output: true Example 2 5 / \ 1 4 / \ 3 6 Output: false Explanation The input is: [5,1,4,null,null,3,6].

by lek tin in "algorithm" access_time 2-min read

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

by lek tin in "algorithm" access_time 2-min read

Kth Smallest Element in a BST

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. Example 1 Input: root = [3,1,4,null,2], k = 1 Output: 1 Example 2 Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3 ``` ### Follow-up What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently?

by lek tin in "algorithm" access_time 2-min read

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1 … n? Example Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 Exaplanation n = 3 root: 1 left: 0 right: 2 f(0)*f(2); root: 2 left: 1 right: 1 f(1)*f(1); root: 3 left: 2 right: 0 f(2)*f(0); Solution class Solution: def numTrees(self, n): """ :type n: int :rtype: int """ res = [1] for i in range(1, n+1): for j in range(i): res.

by lek tin in "algorithm" access_time 1-min read

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. Example Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 Solution # Definition for a binary tree node.

by lek tin in "algorithm" access_time 1-min read