Saturday, March 24, 2018

binary tree iterators

binarytreeIterator:
    stack, prevn
    ctor(tree):
        if tree == null:
            throw
        stack = new
        prevn = null
        if tree.root != null:
            stack.push(tree.root)
    
    bool hasnext():
        return stack.any()
    
    //O(n)
    bool isVisited(n, visited):
        return visited.has(n)
    
    //O(1), and O(logn) due to stack
    bool isVisited(n, prevn):
        return prevn == n
    
    // pre-order
    x current():
        if stack.isEmpty():
            throw "empty"
        n = stack.pop()
        if n.right != null:
            stack.push(n.right)
        if n.left != null:
            stack.push(n.left)
        return n.value
        
    // in-order
    x current():
        if stack.isempty():
            throw "empty"
        while stack.any():
            n, isVisited = stack.pop()
            if !isVisited && n.left != null:
                stack.push(n, isVisited: true)
                stack.push(n.left, isVisited: false)
                continue
            if n.right != null:
                stack.push(n.right, isVisited: false)
            return n
    
    // post-order
    x current():
        if stack.isEmpty():
            throw "empty"
        while stack.any():
            n = stack.pop()
            if n.left != null 
                && !isVisited(n.left, prevn) && !isVisited(n.right, prevn):
                stack.push(n)
                stack.push(n.left)
                continue
            if n.right != null && !isVisited(n.right, prevn):
                stack.push(n)
                stack.push(n.right)
                continue
            prevn = n
            return n.value
        throw "invalid op"
[Hat tip to J]

No comments:

Post a Comment