Interview Question

    Snaking Binary Tree Traversal

Return the list of node values in snake order traversal from a given binary tree.  For instance:

# Input:
#           1
#      2          3
#   4    5     6      7
# Expected Return:
# [1, 3, 2, 4, 5, 6, 7]

Write a psuedo-code response to fit the following template:

class Node {
  def __init__(self, int val, Node left=None, Node right=None) {
      self.val = val
      self.left = left
      self.right = right
  }
}

def snake_order(tree) {
     # YOUR ANSWER HERE
}

n = array()
n[4] = new Node(4)
n[5] = new Node(5)
n[6] = new Node(6)
n[7] = new Node(7)
n[2] = new Node(2, n[4], n[5])
n[3] = new Node(3, n[6], n[7])
n[1] = new Node(1, n[2], n[3])

print(snake_order(n[1]))
# [1, 3, 2, 4, 5, 6, 7]


Answers

  • ▲
    1280
    ▼
    @qassim.mutawa 

    # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def increasingBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        
        def helper(node):
            if node is None: return None, None
            
            if node.left is None and node.right is None:
                return node, node

            left_root, left_end = helper(node.left)
            right_root, right_end = helper(node.right)
            
            first, end = None, None
            
            if left_root:
                first = left_root
                # left_end = node 
                left_end.right = node 
            else:
                first = node
                
            node.left = None
            
            if right_root:
                end = right_end
                node.right = right_root
            else:
                end = node
            
            return first, end
        
        
        return helper(root)[0]

  • ▲
    160
    ▼
    @prince_tukat4ever 

    // C++ implementation of a O(n) time method for 
// Zigzag order traversal 
#include <iostream> 
#include <stack> 

using namespace std; 

  
// Binary Tree node 

struct Node { 

    int data; 

    struct Node *left, *right; 
}; 

  
// function to print the zigzag traversal 

void zizagtraversal(struct Node* root) 
{ 

    // if null then return 

    if (!root) 

        return; 

  

    // declare two stacks 

    stack<struct Node*> currentlevel; 

    stack<struct Node*> nextlevel; 

  

    // push the root 

    currentlevel.push(root); 

  

    // check if stack is empty    

    bool lefttoright = true; 

    while (!currentlevel.empty()) { 

  

        // pop out of stack 

        struct Node* temp = currentlevel.top(); 

        currentlevel.pop(); 

  

        // if not null 

        if (temp) { 

  

            // print the data in it 

            cout << temp->data << " "; 

  

            // store data according to current 

            // order. 

            if (lefttoright) { 

                if (temp->left) 

                    nextlevel.push(temp->left); 

                if (temp->right) 

                    nextlevel.push(temp->right); 

            } 

            else { 

                if (temp->right) 

                    nextlevel.push(temp->right); 

                if (temp->left) 

                    nextlevel.push(temp->left); 

            } 

        } 

  

        if (currentlevel.empty()) { 

            lefttoright = !lefttoright; 

            swap(currentlevel, nextlevel); 

        } 

    } 
} 

  
// A utility function to create a new node 

struct Node* newNode(int data) 
{ 

    struct Node* node = new struct Node; 

    node->data = data; 

    node->left = node->right = NULL; 

    return (node); 
} 

  
// driver program to test the above function 

int main() 
{ 

    // create tree 

    struct Node* root = newNode(1); 

    root->left = newNode(2); 

    root->right = newNode(3); 

    root->left->left = newNode(7); 

    root->left->right = newNode(6); 

    root->right->left = newNode(5); 

    root->right->right = newNode(4); 

    cout << "ZigZag Order traversal of binary tree is \n"; 

  

    zizagtraversal(root); 

  

    return 0;

  • ▲
    128
    ▼ 

    aa

  • ▲
    64
    ▼ 

       for i in item

  • ▲
    64
    ▼
    @dagreatjames 

    1, 3, 2, 4, 5, 6, 7

Interview Questions

This question was recently asked at a major tech company (ie Google, Apple, Facebook, Amazon)
We're compiling a definitive list of interview questions.

Take a practice interview and score yourself.

<< Return to Index