Searching A Binary Tree

Discussion in 'Homework Help' started by razzler, Mar 10, 2008.

  1. razzler

    Thread Starter Member

    Feb 9, 2008

    We are asked to synthesize a sequential circuit whose function is to search on the binary tree the node that is different from the rest(let's say all nodes contain a 1 so we need to look for the node that contains 0). We have to start from a specific node and look in all of the tree's branches and nodes. Upon finding the different node, we traverse back to the start node.

    Basically, it's like trying to solve a maze by backtracking but must be implemented through a sequential circuit.

    I already did a state diagram and a state transition table(see images)



    The problem is, I'm confused of the inputs and outputs. Is the inputs equal to the present and the output to the next state??

    The other problem is, if it comes to an intersection, how does the circuit go back to that intersection if that branch does not have the different node??:confused:

    Btw, all the states are counted but when the state is in A(turn around:meaning, the branch does not contain the different node), the counter starts decrementing until it goes back to the intersection. How do I do this such that it does not decrement all the way back to the start node??

    If you're confused, so am I...PLEASE HELP...I don't want to fail this subject and when I consult the instructor about this, I get more confused and all I get from him is more problems than before.