search spaces if non-none matrix is returnedthen the puzzle is solved and the solution may be printed this is one example where no tree is ever constructedyet the search space is shaped like tree and depth first search can be used to search the problem space summary tree-like structures appear in many problems in computer science tree datatype can hold information and allow quick insertdeleteand search times while binary search trees are not used in practicethe principles governing them are used in many advanced data structures like -treesavl-treesand splay trees understanding how references point to objects and how this can be used to build datatype like tree is an important concept for computer programmers to understand search spaces are often tree-like when making decision between several choices leads to another decision search space is not datatypeso in this case no tree is built howeverthe space that is searched has tree-like structure the key to doing depth first search of space is to remember where you were so you can backtrack when choice leads to dead end backtracking is often accomplished using recursion many algorithms that deal with trees are naturally recursive depth first searchtree traversalsparsingand abstract syntax evaluation may all be recursively implemented recursion is powerful mechanism to have in your toolbox for solving problems review questions answer these short answermultiple choiceand true/false questions to test your mastery of the is the root of tree in computer science at the top or bottom of tree how many roots can tree have full binary tree is tree that is full at each level of the treemeaning there is no room for another node at any level of the treeexcept at the leaves how many nodes are in full binary tree with three levelshow about levelshow about levels in full binary treewhat is the relationship between the number of leaves in the tree and the total number of nodes in the tree when constructing treefor which is it easiest to write codea bottom-up or top-down construction of the tree what term is used when wrong choice is made and another choice must be attempted when searching for value in tree how does search space differ from tree datatypethis copy belongs to 'acha