FilesExpand file tree

 master

/

max_depth_binary_tree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (40 loc) · 904 Bytes

 master

/

max_depth_binary_tree.py

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (40 loc) · 904 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

"""

Problem Statement

=================

Given a binary tree, write a program to find the maximum depth at any given node.

For e.g, for this binary tree.

1

/ \

2 3

/ \

4 5

The height at 1 is 3, and the height at 3 is 2.

"""

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

n1 = Node(1)

n2 = Node(2)

n3 = Node(3)

n4 = Node(4)

n5 = Node(5)

# construct the tree as given in the problem.

n1.left = n2

n1.right = n3

n3.left = n4

n3.right = n5

def find_max_depth(n):

if n is None:

return 0

left_height = find_max_depth(n.left)

right_height = find_max_depth(n.right)

if left_height > right_height:

result = left_height + 1

else:

result = right_height + 1

return result

if __name__ == '__main__':

assert 3 == find_max_depth(n1)

assert 2 == find_max_depth(n3)