Answers.Body: <p>There is always a lot of confusion about this concept, because <em>the naming is misleading, given that <strong>both tree and graph searches produce a tree</strong> (from which you can derive a path) while exploring the search space, which is usually represented as a graph</em>.</p>
  <h3>Differences</h3>
  <p>Firstly, we have to understand that the underlying problem (or search space) is almost always represented as a graph (although the underlying graph may not contain cycles, so it may represent a tree). So, the difference is not whether the problem is a tree (a special kind of graph), or a general graph!</p>
  <p>The distinction is, instead, how we are traversing the search space (represented as a graph) to search for our goal state and whether we are using an additional list (called the <em>closed list</em>) or not.</p>
  <p>So, the basic <strong>differences</strong> are</p>
  <ol>
  <li><p>In the case of a graph search, we use a list, called the <strong>closed list</strong> (also called <strong>explored set</strong>), to keep track of the nodes that have already been visited and expanded, so that they are not visited and expanded again.</p>
  </li>
  <li><p>In the case of a tree search, we do <strong>not</strong> keep this closed list. Consequently, the same node can be visited multiple (or even infinitely many) times, which means that the produced tree (by the tree search) may contain the same node multiple times.</p>
  </li>
  </ol>
  <h3>Advantages and disadvantages</h3>
  <p>The <strong>advantage</strong> of graph search obviously is that, if we finish the search of a node, we will never search it again. On the other hand, the tree search can visit the same node multiple times.</p>
  <p>The <strong>disadvantage</strong> of graph search is that it uses more memory (which we may or may not have) than tree search. This matters because graph search actually has <em>exponential</em> memory requirements in the worst case, making it impractical without either a really good search heuristic or an extremely simple problem.</p>
  <p>So, there is a <strong>trade-off</strong> between space and time when using graph search as opposed to tree search (or vice-versa).</p>
  <h3>Conclusion</h3>
  <p>So, the difference between tree search and graph search is <strong>not</strong> that tree search works on trees while graph search works on graphs! Both can work on trees or graphs (but, given that graphs are a generalization of trees, we can simply say that both work on graphs, either trees or not) and both produce a tree!</p>
  <h3>Notes</h3>
  <p>The definitions of tree search and graph search given above are based on the definitions given in section 3.3 (page 77) of the book <a href="https://faculty.psau.edu.sa/filedownload/doc-7-pdf-a154ffbcec538a4161a406abf62f5b76-original.pdf" rel="noreferrer"><em>Artificial Intelligence: A Modern Approach</em> (3rd edition)</a>, by Stuart J. Russell and Peter Norvig, which is the de-facto standard book in artificial intelligence, so these definitions are applicable in the context of artificial intelligence (which is also the context of this site). <a href="https://github.com/aimacode/aima-pseudocode/blob/master/md/Tree-Search-and-Graph-Search.md" rel="noreferrer">Here</a> you have the pseudocode of tree and graph searches (provided by P. Norvig).</p>
  <p>However, note that, occasionally, people may use the term <em>tree search</em> to refer to a <em>tree traversal</em>, which is used to refer to a search in a <a href="https://en.wikipedia.org/wiki/Search_tree" rel="noreferrer">search tree</a> (e.g., a binary search tree or a red-black tree), which is a tree (i.e. a graph without cycles) that maintains a certain order of its elements. This is another reason for having different definitions of a tree search and to think that a tree search works only on trees.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-18T21:04:48.313Z
Answers.Text: My understanding of tree is that trees are not only a form of directed graph but the nodes are ORDERED, making the tree unique from a graph. Because a tree is ordered, there are no loops. Thus, a node shouldn't ever appear as multiple different nodes of the tree unless the implementer did something very wrong, because keeping track of the list of nodes visited is implicit as part of tree traversal algorithms.
Answers.UserDisplayName: Dunk
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-10T22:41:16.733Z
Answers.Text: @Dunk What do you mean by "a tree is ordered"? Not all trees necessarily have their elements ordered. There are trees, like red-black trees (or, in general, binary search trees), that maintain a certain order of their stored elements, but not all tress maintain a certain order of their elements. So, a tree has no loops not because it is ordered, but because there are no cycles (of the form `A -> B -> A`).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-11T01:26:09.990Z
Answers.Text: @Dunk In a _search_ tree, nodes are ordered, but not in trees in general, except in the sense of depth. Tree search however, is not "search on trees", but a specific family of search algorithms used in AI that are only guaranteed to work on tree structured problems, although they may be applied to other problems (where they may, or may not, fail).
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-16T19:51:52.680Z
Answers.LastActivityDate: 2021-05-15T12:42:48.387Z
Answers.LastEditDate: 2021-05-15T12:42:48.387Z
Answers.UserDisplayName: Amrinder Arora
Body: <p>I have read various answers to this question at different places, but I am still missing something. </p>
  
  <p>What I have understood is that a graph search holds a closed list, with all expanded nodes, so they don't get explored again. However, if you apply breadth-first-search or uniformed-cost search at a search tree, you do the same. You have to keep the expanded nodes in memory. </p>
  
Tags: <comparison><definitions><search><graph-search><tree-search>
Title: What is the difference between tree search and graph search?
UserDisplayName: xava
ThreadText: # What is the difference between tree search and graph search?
  
  (Asked by: username_0 on 2018-05-15)
  
  I have read various answers to this question at different places, but I am still missing something.
  
  What I have understood is that a graph search holds a closed list, with all expanded nodes, so they don't get explored again. However, if you apply breadth-first-search or uniformed-cost search at a search tree, you do the same. You have to keep the expanded nodes in memory.
  
  **Tags:** comparison, definitions, search, graph-search, tree-search
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-12-16. Score: 19
  
  There is always a lot of confusion about this concept, because *the naming is misleading, given that **both tree and graph searches produce a tree** (from which you can derive a path) while exploring the search space, which is usually represented as a graph*.
  
  ### Differences
  
  Firstly, we have to understand that the underlying problem (or search space) is almost always represented as a graph (although the underlying graph may not contain cycles, so it may represent a tree). So, the difference is not whether the problem is a tree (a special kind of graph), or a general graph!
  
  The distinction is, instead, how we are traversing the search space (represented as a graph) to search for our goal state and whether we are using an additional list (called the *closed list*) or not.
  
  So, the basic **differences** are
  
  1. In the case of a graph search, we use a list, called the **closed list** (also called **explored set**), to keep track of the nodes that have already been visited and expanded, so that they are not visited and expanded again.
  2. In the case of a tree search, we do **not** keep this closed list. Consequently, the same node can be visited multiple (or even infinitely many) times, which means that the produced tree (by the tree search) may contain the same node multiple times.
  
  ### Advantages and disadvantages
  
  The **advantage** of graph search obviously is that, if we finish the search of a node, we will never search it again. On the other hand, the tree search can visit the same node multiple times.
  
  The **disadvantage** of graph search is that it uses more memory (which we may or may not have) than tree search. This matters because graph search actually has *exponential* memory requirements in the worst case, making it impractical without either a really good search heuristic or an extremely simple problem.
  
  So, there is a **trade-off** between space and time when using graph search as opposed to tree search (or vice-versa).
  
  ### Conclusion
  
  So, the difference between tree search and graph search is **not** that tree search works on trees while graph search works on graphs! Both can work on trees or graphs (but, given that graphs are a generalization of trees, we can simply say that both work on graphs, either trees or not) and both produce a tree!
  
  ### Notes
  
  The definitions of tree search and graph search given above are based on the definitions given in section 3.3 (page 77) of the book [*Artificial Intelligence: A Modern Approach* (3rd edition)](https://faculty.psau.edu.sa/filedownload/doc-7-pdf-a154ffbcec538a4161a406abf62f5b76-original.pdf), by Stuart J. Russell and Peter Norvig, which is the de-facto standard book in artificial intelligence, so these definitions are applicable in the context of artificial intelligence (which is also the context of this site). [Here](https://github.com/aimacode/aima-pseudocode/blob/master/md/Tree-Search-and-Graph-Search.md) you have the pseudocode of tree and graph searches (provided by P. Norvig).
  
  However, note that, occasionally, people may use the term *tree search* to refer to a *tree traversal*, which is used to refer to a search in a [search tree](https://en.wikipedia.org/wiki/Search_tree) (e.g., a binary search tree or a red-black tree), which is a tree (i.e. a graph without cycles) that maintains a certain order of its elements. This is another reason for having different definitions of a tree search and to think that a tree search works only on trees.
  
  > **Comments:**
  > **username_2**: My understanding of tree is that trees are not only a form of directed graph but the nodes are ORDERED, making the tree unique from a graph. Because a tree is ordered, there are no loops. Thus, a node shouldn't ever appear as multiple different nodes of the tree unless the implementer did something very wrong, because keeping track of the list of nodes visited is implicit as part of tree traversal algorithms.  
  > **username_3**: @username_2 What do you mean by "a tree is ordered"? Not all trees necessarily have their elements ordered. There are trees, like red-black trees (or, in general, binary search trees), that maintain a certain order of their stored elements, but not all tress maintain a certain order of their elements. So, a tree has no loops not because it is ordered, but because there are no cycles (of the form `A -> B -> A`).  
  > **username_4**: @username_2 In a _search_ tree, nodes are ordered, but not in trees in general, except in the sense of depth. Tree search however, is not "search on trees", but a specific family of search algorithms used in AI that are only guaranteed to work on tree structured problems, although they may be applied to other problems (where they may, or may not, fail).  
  
  ---
  
  