We're programming a lego NXT robot in my embedded systems class and basically our robot has to search through a tree (following a black path using its light sensor). My question is, what is the best way of searching through a tree (I know binary trees exist, but I'm not quite sure how to program the robot using it). Any ideas would help!

Thanks

 

Ummmmm, whaT? What kind of tree, and what are you searching for? what methods of input sensors and locomotion are being used?

 

Its sort of like a binary tree.
I'm searching for a CD (very reflective material) at the end of the tree.
Methods for input: Light Sensors
Methods for moving: Motors (each wheel can be given its own respective power).

Basically if the light sensor detects black, it'll move. But how do I start going through each branch on the tree??

 

A tree search is fundamentally different from following a line. It might be useful in maze solving - http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/binarySearchTree.htm

 

A binary tree of what size and height?
what is the root node?
Is it sorted or Balanced or neither?
The questions can go on an on here so can you be a little more specific?

There are tons of binary tree types that you would have to be taken in consideration :

Types of binary trees

• A rooted binary tree is a rooted tree in which every node has at most two children.
• A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.
• A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level.[1] (This is ambiguously also called a complete binary tree.)
• A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.[2]
• An infinite complete binary tree is a tree with levels, where for each level d the number of existing nodes at level d is equal to 2d. The cardinal number of the set of all nodes is
  
  . The cardinal number of the set of all paths is
  
  .
• A balanced binary tree is where the depth of all the leaves differs by at most 1. Balanced trees have a predictable depth (how many nodes are traversed from the root to a leaf, root counting as node 0 and subsequent as 1, 2, ..., depth). This depth is equal to the integer part of log2(n) where n is the number of nodes on the balanced tree. Example 1: balanced tree with 1 node, log2(1) = 0 (depth = 0). Example 2: balanced tree with 3 nodes, log2(3) = 1.59 (depth=1). Example 3: balanced tree with 5 nodes, log2(5) = 2.32 (depth of tree is 2 nodes).
• A rooted complete binary tree can be identified with a free magma.
• A degenerate tree is a tree where for each parent node, there is only one associated child node. This means that in a performance measurement, the tree will behave like a linked list data structure.

A rooted tree has a top node as root.

Do you already have the tree planned out? How wide are the lines? can you post it on here or atleast a sketch of it, it can be drawn on paper and scanned in if needed, but it would be very helpful in guiding you.

Do you have any of the electronics? Such as motors? Microcontroller, etc.?

B. Morse