forked from mission-peace/interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmax_depth_binary_tree.py
More file actions
54 lines (40 loc) · 904 Bytes
/
max_depth_binary_tree.py
File metadata and controls
54 lines (40 loc) · 904 Bytes
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)