0

This was asked to me in a recent interview. Binary tree is stored in database in the following schema

Table tree ( int nodeId, int parentId, int data)

This is a self referencing table. I was asked to write query to print the data of all nodes in the path from the root to the given node. Is it possible to do it in one query?

The solution I gave was loading all the rows to a hashMap with key as nodeId and value as parentId and print the path to the root from the given node using the map.

I can write nested queries to print this if I know the depth of the node in the binary tree. Sample query to print all the nodes from root to a node with nodeId='4' which is at depth 2 is as follows: "select n.data, n1.data, n2.data from Tree n where nodeId in (select parentId from Tree n1 where nodeId in (select pId from Tree n2 where nodeId='4')); "

Is it possible to do this without using nested queries? If so what query I can use to do this?

Bourne
  • 1,905
  • 13
  • 35
  • 53
  • Suggestions: 1. Add this to the end of your question: "If it is possible, how?". 2. Try to write the query yourself... we can help you with the details once you take the first step – Barranka Jun 02 '13 at 13:07
  • I have edited the question. For the solution if I know the depth of the node in the tree then I can come up with a nested query like below: – Bourne Jun 02 '13 at 14:32
  • Suppose the binary tree is like 1, a 2, b 3, c 4, d 5, e – Bourne Jun 02 '13 at 14:34
  • where in (a, b) a is the nodeId and b is the data. and if the input nodeId = 4 The query would look like select n.data, n1.data, n2.data from Tree n where nodeId in (select parentId from Tree n1 where nodeId in (select pId from Tree n2 where nodeId='4')); This should print all the data from the root to the node with nodeId 4. But here I know the depth and I can write the nexted query. – Bourne Jun 02 '13 at 14:37
  • Not sure how I can solve this without using the nested query? i.e. without knowing the depth of the node in advance. – Bourne Jun 02 '13 at 14:38
  • The structure of the binary tree for which I came up with the above query is below ..(1, a)... | | ..(2,b) (3, c) | ..(4,d) – Bourne Jun 02 '13 at 14:41
  • Ahhh.. I'm not able to draw the binary tree here. When I hit add comment it removes all the new line characters from the comment. – Bourne Jun 02 '13 at 14:42
  • @bourne: Which database? Most modern RDBMSs (SQLServer, Oracle 11g, PostgreSQL) have *recursive* Common Table Expressions, which are ideal for this; older versions of Oracle could use the `connect by` syntax to achieve the same result. On the other hand, I don't know how this could be achieved in MySQL or SQLite without using procedural code. –  Jun 02 '13 at 15:51
  • I want to achieve this in MySql. Is it possible to achieve in Oracle? How can I achieve it using procedural code? – Bourne Jun 02 '13 at 16:45
  • Yes, it's possible in a single query in Oracle - which version, 11g or earlier? You can find out how to do this in a procedure in MySQL in the answer to this question: http://stackoverflow.com/a/11035966/359040 –  Jun 02 '13 at 20:07
  • How can I do it in 11G? – Bourne Jun 03 '13 at 06:05

0 Answers0