Binary word trees

Question

I have barely squeaked by my last cs class and now I am in data structures. I am building a binary tree structure from scratch and I am a little confused on how the iterator will work. I understand how they work in double linked lists, but am not sure how this one will work................ thanks.

Answer 1

What do you mean by "Iterator"? If you just have to iterate the tree, you can do that recursively: http://en.wikipedia.org/wiki/Tree_traversal#Sample_implementations

If you have to provide an IEnumerator interface like in C# or Java or want to save stack space, use this: http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal You could use yield in C# or easily transform the while loop into the "GetNext" method needed for an iterator.

Answer 2

I can do it recursively. I am just trying to picture in my head how you move from leaf to leaf since starting at the root there is 2 choices of where to go next and after that it just increases 2^n times. This order of how this works is what is confusing me.

Answer 3

There are 2 main ways of iterating through a tree. I posted some sample Python code of how to do it at http://stackoverflow.com/questions/754439/iterative-tree-walking/754448#754448.

Answer 4

In binary tree every node would store some value and have 2 children, for example left and right. Now one way to traverse the tree is to start from top, traverse left child, look at this node's value and then traverse right child.

Where traverse a child means (recursively): 1) traverse left child 2) look at node's value 3) traverse right child

This is a depth first traversal, so for each node you 'use' or 'see' the value of it's left child first, then the value of the current node and the last the value of right child.

For breadth first traversal you would start from root, look at node's value and then push it's children (if they exist) into a queue. Then loop while there's a node in the queue, get node from the front of the queue and repeat: look at it's value, if it has children then push them at the end of queue.

Example in python:

#!/usr/bin/env python

    class Node:
        def __init__(self, val = 0):
            self.value = val
            self.left = None
            self.right = None

        def __str__(self):
            return "%d" % (self.value)

    def dfs(node = None):
        if node is None: return

        dfs(node.left)
        print node
        dfs(node.right)

    def bfs(root = None):
        if root is None: return

        nodes = []
        nodes.append(root)

        while len(nodes):
            current = nodes[0]
            print current
            nodes.remove(current)

        if current.left is not None:
            nodes.append(current.left)
        if current.right is not None:
            nodes.append(current.right)

    def main():
        root = Node(0)
        root.left = Node(10)
        root.right = Node(20)

        l = root.left
        l.left = Node(100)
        l.right = Node(101)

        r = root.right
        r.left = Node(200)
        r.right = Node(201)

        dfs(root)
        bfs(root)


    if __name__ == '__main__':
        main()



# example tree constructed:
#            0
#      10        20
#  100   101  200  201

# dfs (depth first) traversal:
# 100
# 10
# 101
# 0
# 200
# 20
# 201

# bfs (breadth first) traversal:
# 0
# 10
# 20
# 100
# 101
# 200
# 201

Answer 5

I had this same issue in my Data Structures class.

My solution is fairly simple.

Traverse the tree recursively, but store each node you visit in another collection, and then iterate that new collection. That way, there's nothing tricky about writing the iterator at all.

I personally chose to use a stack, but you could do it with a simple array, or even a linked list (Which you said you already have experience with).

Answer 6

All the other answers are technical discussions on how to implement an iterator over a tree structure. However, as I understand your question, you seem to be having trouble with comprehending the mechanics of the concept of tree traversal, and not just the implementation. In other words, you don't "grok" tree traversal. What will probably help more than anything is to get a good pseudo-code algorithm for traversing a binary tree, a pencil, a sheet of paper, and work out an example. Build a simple binary tree and then traverse it by mechanically following the pseudo code yourself. You should probably use a second sheet of paper for writing out the stack. That is, the state of every function that is in the middle of being called because it is waiting for a sub-function to return.

Keep in mind, while you are doing this, that a tree is a very elegant structure. It can seem quite complex, but at every node it is simple. To perform an operation on all elements in a tree, you merely perform that operation at the root of the tree and then have the operation call itself on each child of that root, which are themselves roots of sub-trees. Working out an example yourself will go a long ways towards getting your mind to understand and embrace recursion. Don't be bewildered if you find it hard. Recursion is weird. It is a hard concept at first, but it is necessary to understand and work with trees.

Here is an example (ASCII art) tree you could use to start:

      F
    /   \
   /     \
   D      H
 /  \    / \
 B   E  G   I
/ \
A  C

And a simple pseudo code algorithm that you can use for writing all letters in a correct in-order traversal.

procedure traverse(node)
    if node is not null:
        traverse(node.left)
        write node.letter
        traverse(node.right)
    else:
        do nothing

You may even start out with simpler trees. What if the tree only consisted of nodes D, F, and H? What if it was only F? Null? Try those simple examples and work up to the bigger tree. By the time you have worked out how to do this consistently and correctly, you will not only have a really good feeling for what is going on in the iterator implementation, you will have a much better appreciation for the power of recursion.