Traverse through binary tree to change the value of each nodes?

Question

I'm trying to transverse through a binary tree to add "newvalue" to each nodes current value.

def(node, 2):

Before:

After:

How should I approach this recursively?!

Cant you just do a pre/post/inorder traversal and just update values? — smk
– smk, Commented Mar 8, 2013 at 5:07

Ashwin Balamohan · Accepted Answer · 2013-03-08 06:13:08Z

Harold provided a very clean and general example. Here's a take, with annotations, that will work for a binary tree

With a recursive algorithm, you've got to think of two things: 1. The base case 2. The recursive call

In your example: - Base case = Node has no children. No recursive calls will take place - Recursive call = Each node is its own mini-tree, so call the function on each child

def increase_tree_values(node, delta):
    """ Increases/decreases the value of all nodes in the tree by the value 'delta'
    """

    # increase the current node's value
    node.value += delta

    # recursively call function on left child, if it exists
    if node.left_child:
        increase_tree_values(node.left_child, delta)

    # recursively call function on right child, if it exists
    if node.right_child:
        increase_tree_values(node.right_child, delta)



# presuming you have some binary tree called 'tree' already constructed
# increase all nodes in 'tree' by 2
increase_tree_values(tree, 2)

Let me know if you have any questions. If this exercise was presented to you in school, they're really just trying to get you to identify this as a simple tree traversal, where you change the value of the nodes as you traverse through the tree. What I would recommend is for you to try your hand at programming all the different tree traversals without any notes. You'll learn a lot about trees and recursion that way.

Thanks for the clarifications, just a beginner here. I can do it with iteration but recursive confused me good.
No problem. It takes a while to get a hang of, but I guarantee you that it's worth the effort. My first year professor put it in terms of set theory, where some sets are often defined in terms of their subsets. Of course, this could lead to an infinite regression, so you need a base case to know when to stop. Also, it's good to upvote and accept answers that you find helpful. The people who answer them get "reputation points", which keeps the wheels of Stackoverflow churning ;-)
Consider this link: ibm.com/developerworks/library/l-recurs/index.html

gukoff · Accepted Answer · 2013-03-08 05:08:30Z

1

def add_value(node, delta):
    node.value += delta
    for child in node.children:
        add_value(child, delta)

answered Mar 8, 2013 at 5:08

gukoff

2,2703 gold badges19 silver badges30 bronze badges

2 Comments

mtk Over a year ago

Do add some explanation as well, to make it a better answer.

gukoff Over a year ago

The code should have commentaries if it does'nt explain itself. This code does.

Collectives™ on Stack Overflow

Traverse through binary tree to change the value of each nodes?

2 Answers 2

3 Comments

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Related