about summary refs log tree commit diff
path: root/scratch/facebook/second-largest-item-in-bst.py
blob: 2815dec9ee6055e3ea29c6c4fb3f58bca4162fd9 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import deque
from node import Node, tree

def find_largest(node):
    while node.right:
        node = node.right
    return node.value

def find_second_largest(node):
    # parent of the rightmost, when rightmost is leaf
    # max(rightmost.left)
    prev = None
    while node.right:
        prev = node
        node = node.right
    if node.left:
        return find_largest(node.left)
    else:
        return prev.value

assert find_second_largest(tree) == 72
print("Success!")