Lowest Common Ancestor of a Binary Search Tree

0
votes

I understand the algorithm for the iterative approach of finding LCA of a BST. But I do not understand the line below in BOLD. Could anyone please explain to me?

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while (root.val - p.val) * (root.val - q.val) > 0:
            root = (root.left, root.right)[p.val > root.val]
        return root
1
pythonbinary-tree

1 Answers

1
votes

As I understand you need explanation of this line.

root = (root.left, root.right)[p.val > root.val]

It creates tuple with two elements: root.left and root.right, they have index 0 and 1. p.val > root.val is a boolean expression. if is false(for python this is 0) it selects root.left(e.g. first element in tuple). if it is true(for python this is 1) is selects root.right(e.g. second element in tuple).

This is because

>>> False == 0
True
>>> True == 1
True