I try to collect problems about Binary Search Tree (BST) which are asked in interview frequently.

Basicly, here is the definition of Binary Search Tree. And I show the way how to implement the basic operation like insert, delete and so on.

1

2

3

4

5

classTreeNode() :

def__init__(self, num = -1) :

self.val = num

self.right = None

self.left = None

You could find all my practices with BST in github: BST

There are three different ways to travel a BST. N(node), L(left subtree), R(right subtree)

NLR: Firstly the traveller access the data of the Node(N) and then it enter into the left sub-tree, travel the right sub-tree

LNR

LRN

It’s very easy and obvious to implement the recursive definition of the three different traveller.

You will find that it’s a very efficient way to understand what means Pre-traveller, In-traveller and Post-traveller.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

"""

Recursive definition

"""

defpre_traveller(self, node):

if node == None :

returnNone

print node.val

self.pre_traveller(node.left)

self.pre_traveller(node.right)

defin_traveller(self, node):

if node == None:

returnNone

self.in_traveller(node.left)

print node.val

self.in_traveller(node.right)

defpost_traveller(self, node):

if node == None:

returnNone

self.post_traveller(node.left)

self.post_traveller(node.right)

print node.val

But the interview officer may not be satisfy with your recursive implementation. Take some time to understand the iteratly implementation below there.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

"""

Iterately implementation

Given a binary tree, return the preorder traversal of

its nodes' values.

"""

defpreorderTraversal(self, root):

"""

:type root: TreeNode

:rtype: List[int]

"""

if root isNone:

return []

stack = [root]

ret = []

while len(stack) != 0:

node = stack.pop()

ret.append(node.val)

if node.right isnotNone:

stack.append(node.right)

if node.left isnotNone:

stack.append(node.left)

return ret

"""

Given a binary tree, return the inorder traversal

of its nodes' values.

"""

definorderTraversal(self, root):

res, stack = [], []

whileTrue:

while root:

stack.append(root)

root = root.left

ifnot stack:

return res

node = stack.pop()

res.append(node.val)

root = node.right

defpostorderTraversal(self, root):

"""

:type root: TreeNode

:rtype: List[int]

"""

res = []

stack = [root]

while len(stack):

node = stack.pop()

if node:

res.append(node.val)

stack.append(node.left)

stack.append(node.right)

return res[::-1]

There is another interesting problem that how to travel a BST in level order. Something like this: For example:

Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

At this moment, you should try to use some basic data structure to solve this problem. Don’t forget STACK :)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

"""

Given a binary tree, return the level order traversal of

its nodes' values. (ie, from left to right, level by level).

"""

deflevelOrder(self, node):

if node isNone:

return []

stack = [node]

length = len(stack)

ret = []

j = 0

while length != 0:

ret.append([])

for i in range(0, length):

ret[j].append(stack[i].val)

if stack[i].left != None:

stack.append(stack[i].left)

if stack[i].right != None:

stack.append(stack[i].right)

for i in range(0, length):

stack.remove(stack[0])

length = len(stack)

j += 1

return ret

After you solve this problem, you have knew that stack is a efficient and useful ADT. Once you meet a hard problem, try to use another ADT to solve your problem.

Function isValidBST help us to check whether the tree is a BST. Now, if you have no idea about what means a BST, go to wikipedia and help yourself :)

You know that if we travel the tree with In-Order traveller, the output of the traveller is sorted from small element to big one.

1

2

3

4

5

6

7

8

9

defisValidBST(self, root):

A = []

A = self.in_traveller(self.root)

for i in range(0, len(A)):

if A[i-1] >= A[i]:

returnFalse

returnTrue

There is a joke about how to invert a BST.

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

It’s easy to solve this problem by recursion.

1

2

3

4

5

6

7

8

definvertTree(self, root):

if root isNone:

return

root.left, root.right = root.right, root.left

self.invertTree(root.left)

self.invertTree(root.right)

You may also be asked to translate a sorted array into BST. So, how to make it?