16.20 - Breadth First and Depth First Searches - Teradata Database - Teradata Vantage NewSQL Engine

Teradata Vantage™ SQL Data Definition Language Detailed Topics

Product
Teradata Database
Teradata Vantage NewSQL Engine
Release Number
16.20
Release Date
March 2019
Content Type
Programming Reference
Publication ID
B035-1184-162K
Language
English (United States)

Hierarchical trees can be traversed either breadth first or depth first. These searches are abbreviated as indicated by the following table.

Abbreviation Definition
BFS Breadth first search

See Breadth First Reporting.

DFS Depth first search

See Depth First Reporting.

In a BFS, each immediate child of a node is visited before any of its grandchildren.

In a DFS, all descendants of each immediate node in the graph are visited before visiting other immediate children of that node.

Consider the following graph of a parts hierarchy.



If this graph is searched breadth first, its nodes are visited in the following order.

      p1   p2   p3   p4   p5   p6   p7   p8   p9   p10   p11   p12

In contrast, if the graph is searched depth first, its nodes are visited in the following order.

      p1   p2   p5   p6   p7   p3   p8   p9   p4   p10   p11   p12

The real effect of specifying a BFS versus a DFS is the ordering of the result set. As a result, it is simple to simulate a BFS or a DFS by simple ordering of the output.