Posts published in “Tree”

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
3
/ \
1   4
\
2
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3   6
/ \
2   4
/
1
Output: 3


What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Solution: Inorder traversal

Time complexity: O(n)
Space compleixty: O(n)

C++

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. 1 <= preorder.length <= 100
2. The values of preorder are distinct.

Solution: Recursion

Time complexity: O(n^2)
Space complexity: O(n)

C++/iterator

We are given the root node of a maximum tree: a tree where every node has a value greater than any other value in its subtree.

Just as in the previous problem, the given tree was constructed from an list A (root = Construct(A)) recursively with the following Construct(A) routine:

• If A is empty, return null.
• Otherwise, let A[i] be the largest element of A.  Create a root node with value A[i].
• The left child of root will be Construct([A[0], A[1], ..., A[i-1]])
• The right child of root will be Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
• Return root.

Note that we were not given A directly, only a root node root = Construct(A).

Suppose B is a copy of A with the value val appended to it.  It is guaranteed that B has unique values.

Return Construct(B).

Example 1:

Input: root = [4,1,3,null,null,2], val = 5
Output: [5,4,null,1,3,null,null,2]
Explanation: A = [1,4,2,3], B = [1,4,2,3,5]


Example 2:

Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]
Explanation: A = [2,1,5,4], B = [2,1,5,4,3]


Example 3:

Input: root = [5,2,3,null,1], val = 4
Output: [5,2,4,null,1,3]
Explanation: A = [2,1,5,3], B = [2,1,5,3,4]


Note:

1. 1 <= B.length <= 100

Solution: Recursion

Since val is the last element of the array, we compare root->val with val, if root->val > val then val can be inserted into the right subtree recursively, otherwise, root will be the left subtree of val.

Time complexity: O(n)
Space complexity: O(n)

C++

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false


Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true


Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Note:

1. The number of nodes in the tree will be between 2 and 100.
2. Each node has a unique integer value from 1 to 100.

Solution: Preorder traversal

Time complexity: O(n)
Space complexity: O(n)

Python3

Given the root of a binary tree, each node has a value from 0 to 25representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

(As a reminder, any shorter prefix of a string is lexicographically smaller: for example, "ab" is lexicographically smaller than "aba".  A leaf of a node is a node that has no children.)

Example 1:

Input: [0,1,2,3,4,3,4]
Output: "dba"


Example 2:

Input: [25,1,3,1,3,0,2]


Example 3:

Input: [2,2,1,null,1,0,null,0]
Output: "abc"


Note:

1. The number of nodes in the given tree will be between 1 and 1000.
2. Each node in the tree will have a value between 0 and 25.

Solution: Recursion

Time complexity: O(n^2)
Space complexity: O(n^2)

Python3

Mission News Theme by Compete Themes.