Iterate/traverse BST Python

Question

I am trying to **find and sum ** all numbers in spesific range low - high in BST. I have accessed just the two numbers under the top of the tree. How to access all other numbers. When tried to iterate or traverse, I received errors.

`

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:

    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        output = 0
        
        if  root.left.val >= low and root.left.val <= high:
            output += root.left.val
        if  root.right.val >= low and root.right.val <= high:
            output += root.right.val
        return output

`

In addition to recursion, take advantage of the structure of a BST. For example, every value in the left subtree is less than root.val. If root.val < low, you know that every value in root.left is also less than low, and so there's no need to recurse on the left subtree: you already know the answer will be 0. — chepner
– chepner, Commented Dec 8, 2022 at 14:11

nokla · Accepted Answer · 2022-12-08 13:41:19Z

1

You have to use a recursive function:

def sum_tree(root, low, high):
    value = root.value
    if value < low or value > high:
        value = 0
    if root.left == None and root.right == None:
        return value
    if root.left == None:
        return value + sum_tree(root.right, low, high)
    if root.right == None:
        return value + sum_tree(root.left, low, high)
    return value + sum_tree(root.left, low, high) + sum_tree(root.right, low, high)

Example:

nodes =[5, 6, 6,7, 2, 10, 5, None, 4, 13]
binary_tree = binarytree.build(nodes)

print(binary_tree)
print("Sum min-max:",sum_tree(binary_tree, 5, 10))

Results:

      _____5___
     /         \
  __6___       _6
 /      \     /  \
7       _2   10   5
 \     /
  4   13

Sum min-max: 39

edited Dec 8, 2022 at 13:41

answered Dec 8, 2022 at 13:36

nokla

1,5981 gold badge6 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

jackal · Accepted Answer · 2022-12-08 13:42:55Z

0

As @nokla has said, you ideally want a recursive approach to this. Here's a variation on the recursive approach that's quite efficient:

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        _sum = 0
        def traverse(n):
            nonlocal _sum
            if n:
                if low <= n.val <= high:
                    _sum += n.val
                traverse(n.left)
                traverse(n.right)
        traverse(root)
        return _sum

answered Dec 8, 2022 at 13:42

jackal

29.1k3 gold badges10 silver badges28 bronze badges

5 Comments

Nikoi Nikoi Over a year ago

Thank you very much. So i need a function inside rangeSumBST to make this work? Could you explain to me the steps of your code, so I can understand the logic? What is nonlocal _sum? Is n the tree? I would rate your code 10/10, but I am not allowed :(

jackal Over a year ago

@NikoiNikoi docs.python.org/3/reference/simple_stmts.html#nonlocal

Nikoi Nikoi Over a year ago

Why is traverse(root) outside the function and how does _sum adds its value?

trincot Over a year ago

A pity that this function will always visit all nodes. The answer from nokla is better in this respect.

jackal Over a year ago

@trincot Unfortunately my pathetic answer was Accepted otherwise I would have deleted it

Collectives™ on Stack Overflow

Iterate/traverse BST Python

2 Answers 2

Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related