Kth Smallest Element in a BST
in Programming on Tree, Interview, Python
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
Follow up: 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?
HINT: Inorder Traversal
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
count = 0
stack = []
node = root
if root == None:
return None
while (len(stack)>0) or (node!=None):
if node!=None:
stack.append(node)
node = node.left
else:
inorder_node = stack.pop()
count += 1
if count == k:
return inorder_node.val
node = inorder_node.right
return None
Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes’ values.
Example :
Given binary tree
1
\
2
/
3
return [3,2,1].
Using recursion is not allowed.
class Solution:
# @param A : root node of tree
# @return a list of integers
def peek(self, stack):
if len(stack) > 0:
return stack[-1]
return None
def postorderTraversal(self, root):
stack = []
ans = []
while 1:
while root:
if root.right:
stack.append(root.right)
stack.append(root)
root = root.left
root = stack.pop()
if root.right and self.peek(stack) == root.right:
stack.pop()
stack.append(root)
root = root.right
else:
ans.append(root.val)
root = None
if len(stack) == 0:
break
return ans
Shortest Unique Prefix
Find shortest unique prefix to represent each word in the list.
Example:
Input: [zebra, dog, duck, dove]
Output: {z, dog, du, dov}
where we can see that
zebra = z
dog = dog
duck = du
dove = dov
NOTE : Assume that no word is prefix of another. In other words, the representation is always
Key: Make a trie, add string to trie, count the frequencies of character at each trie node. Travel the trie, return prefix when found a trie node with frequency = 1
class TrieNode:
def __init__(self):
self.leaves = {}
self.freq = 1
class Trie:
def __init__(self):
self.root = TrieNode()
def insert_word(self, word):
node = self.root
leaves = self.root.leaves
for ch in word:
if ch not in leaves.keys():
leaves[ch] = TrieNode()
node.leaves = leaves
else:
leaves[ch].freq += 1
node = leaves[ch]
leaves = leaves[ch].leaves
def get_prefix(self, word):
leaves = self.root.leaves
prefix = ''
for ch in word:
if leaves[ch].freq==1:
prefix += ch
return prefix
else:
prefix += ch
leaves = leaves[ch].leaves
return prefix
class Solution:
# @param A : list of strings
# @return a list of strings
def prefix(self, A):
prefixes = []
trie = Trie()
for a in A:
trie.insert_word(a)
for a in A:
prefixes.append(trie.get_prefix(a))
return prefixes
Sum Root to leaf number
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers % 1003.
Example :
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13.
Return the sum = (12 + 13) % 1003 = 25 % 1003 = 25.
class Solution:
# @param A : root node of tree
# @return an integer
def sumNumbers(self, A):
if A==None:
return 0
stack = [(A, A.val)]
nums = []
while len(stack) > 0:
node, val = stack.pop()
r = node.right
l = node.left
if l == None and r == None:
nums.append(val)
continue
if r != None:
new_val = val * 10 + r.val
stack.append((r, new_val))
if l != None:
new_val = val * 10 + l.val
stack.append((l, new_val))
return sum(nums) % 1003
