0
What else can I help you with?
Why recursive solution is better for tree traversal?
Because a tree is a recursive data-structure. It's easier to write (and easier to understand) a recursive program for handling it.
Why is there no threading for post order traversal of a binary search tree?
You don't need it. Think about it, you can just use a stack (or a recursive function.)
Write the algorithm for in order traversal?
Inorder(p) { If p = nil return; Inorder(p.left) process(p.data) Inorder(p.right) }
How do you print all data in a Binary Search Tree?
By using Depth First Search or Breadth First search Tree traversal algorithm we can print data in Binary search tree.
Which of the following traversal is used for printing the keys of binary search tree in ascending order?
In order traversal is used.
What is the significance of the reverse postorder traversal in binary trees?
Reverse postorder traversal in binary trees is significant because it allows for efficient processing of nodes in a specific order: right child, left child, root. This traversal method is useful for tasks like deleting nodes or evaluating expressions in a tree structure.
Why recursive solution is better for tree traversal?
Because a tree is a recursive data-structure. It's easier to write (and easier to understand) a recursive program for handling it.
Why is there no threading for post order traversal of a binary search tree?
You don't need it. Think about it, you can just use a stack (or a recursive function.)
Explain the three types of tree traversals with illustration?
Inorder Traversal void inorder(tree t) { if(t == NULL) return; inorder(t->left); printf("%d ", t->val); inorder(t->right); }Preorder Traversalvoid preorder(tree t) { if(t == NULL) return; printf("%d ", t->val); preorder(t->left); preorder(t->right); } Postorder Traversalvoid postorder(tree t) { if(t == NULL) return; postorder(t->left); postorder(t->right); printf("%d ", t->val);
What graph traversal algorithm uses a queue to keep track of vertices which need to be processed?
Breadth-first search
What is the relationship between Dijkstra's algorithm and breadth-first search in graph traversal?
Dijkstra's algorithm is a more advanced version of breadth-first search in graph traversal. While both algorithms explore nodes in a graph, Dijkstra's algorithm considers the weight of edges to find the shortest path, whereas breadth-first search simply explores nodes in a level-by-level manner.
Write the algorithm for in order traversal?
Inorder(p) { If p = nil return; Inorder(p.left) process(p.data) Inorder(p.right) }
How do you write a c program for expression tree traversal?
#include<stdio.h> #include<conio.h> #define MAX 30 typedef struct ETREE { struct ETREE *lc; char data; struct ETREE *rc; }etree; typedef struct STACK { etree *ST[MAX]; int top; }stack; void initialize_stack(stack *sp) { sp->top = -1; } int isstackempty(int top) { if(top MAX - 1) return(1); else return(0); } void push(stack *sp,etree *x) { if(!isstackfull(sp->top)) { sp->top = sp->top + 1; sp->ST[sp->top] = x; } else printf("\n\nStack full!!"); } etree *pop(stack *sp) { etree *x; if(!isstackempty(sp->top)) { x = sp->ST[sp->top]; sp->top = sp->top - 1; return(x); } else return(NULL); } etree *getnode(char d) { etree *node; node = (etree *)malloc(sizeof(etree)); node->lc = NULL; node->data = d; node->rc = NULL; return(node); } etree *construct_etree_from_postfix_exp(char pos[]) { int i; stack s; etree *root = NULL,*node; initialize_stack(&s); for(i=0;pos[i] != '\0';i++) { node = getnode(pos[i]); if(isalpha(pos[i])) { push(&s,node); } else //operator { node->rc = pop(&s); node->lc = pop(&s); push(&s,node); } } root = pop(&s); return(root); } void inorder(etree *temp) { if(temp!= NULL) { inorder(temp->lc); printf("%c",temp->data); inorder(temp->rc); } } void preorder(etree *temp) { if(temp!= NULL) { printf("%c",temp->data); preorder(temp->lc); preorder(temp->rc); } } void postorder(etree *temp) { if(temp!= NULL) { postorder(temp->lc); postorder(temp->rc); printf("%c",temp->data); } } void inorder_nonrec(etree *root) { stack s; etree *temp; temp = root; initialize_stack(&s); while(temp!=NULL s.top!= -1) { while(temp!=NULL) { push(&s,temp); temp = temp->lc; } temp = pop(&s); printf("%c",temp->data); temp = temp->rc; } } void preorder_nonrec(etree *root) { stack s; etree *temp; temp = root; initialize_stack(&s); while(temp!=NULL s.top!= -1) { while(temp!=NULL) { printf("%c",temp->data); push(&s,temp); temp = temp->lc; } temp = pop(&s); temp = temp->rc; } } void postorder_nonrec(etree *root) { stack s; etree *temp; int i,k=0; char A[30]; temp = root; initialize_stack(&s); while(temp!=NULL s.top!= -1) { while(temp!=NULL) { A[k++] = temp->data; push(&s,temp); temp = temp->rc; } temp = pop(&s); temp = temp->lc; } for(i=k-1;i>=0;i--) { printf("%c",A[i]); } } void main() { char pos[30]; etree *root = NULL; int ch; do { clrscr(); printf("\n Choice 1: Create Etree from postfix expression "); printf("\n Choice 2: Recursive inorder,preorder & postorder traversal"); printf("\n Choice 3: Nonrecursive inorder,preorder & postorder traversal"); printf("\n Choice 4: exit "); printf("\n Enter your choice: "); scanf("%d",&ch); switch(ch) { case 1: printf("\n\nEnter the postfix expression : "); scanf("%s",pos); root = construct_etree_from_postfix_exp(pos); printf("\n\nExpression tree created successfully !!"); break; case 2: printf("\n Inorder traversal is : "); inorder(root); printf("\n preorder traversal is : "); preorder(root); printf("\n postorder traversal is : "); postorder(root); getch(); break; case 3: printf("\n Inorder traversal (nonrecursive) : "); inorder_nonrec(root); printf("\n Preorder traversal (nonrecursive) : "); preorder_nonrec(root); printf("\n Postorder traversal (nonrecursive) : "); postorder_nonrec(root); getch(); break; case 4: printf("\n \t**End of program** \n \t\tThank you\n"); break; default:printf("\n invalid choice try again!!!!"); } getch(); }while(ch!=4); } Written by: Fabianski Benjamin
How can you design an algorithm to check if a given graph is connected?
Use a simple DFS/BFS traversal. If you have gone through all nodes, the graph is connected.
What are the advantages and disadvantages of binary trees?
1. This makes the Tree more complex. as we need to keep the record of node's Predecessor and successor 2. Postorder traversal is too complex and there might be changes of errors when both the child are not present & both values of nodes pointer to their Predecessor. -Snehal Javheri
How do you print all data in a Binary Search Tree?
By using Depth First Search or Breadth First search Tree traversal algorithm we can print data in Binary search tree.
How does n-ary tree traversal work and what are the different strategies for traversing an n-ary tree efficiently?
N-ary tree traversal involves visiting each node in an n-ary tree in a specific order. The different strategies for efficiently traversing an n-ary tree include: Preorder traversal: Visit the current node first, then recursively visit each child node in order. Postorder traversal: Recursively visit each child node first, then visit the current node. Level order traversal: Visit nodes level by level, starting from the root and moving down each level before moving to the next level. These strategies help efficiently navigate through the nodes of an n-ary tree while ensuring that each node is visited exactly once.
