Binary Tree

Python



In [3]:

    
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

if __name__ == '__main__':
    rootNode = TreeNode(5)
    rootNode.left = TreeNode(4)
    rootNode.right = TreeNode(6)
    print rootNode.val
    print rootNode.left.val
    print rootNode.right.val

C++

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL){}
};

Tree traversal

Python



In [6]:

    
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

class Traversal(object):
    def __init__(self):
        self.traverse_path = list()
        
    def preorder(self, root):
        if root:
            self.traverse_path.append(root.val)
            self.preorder(root.left)
            self.preorder(root.right)
    
    def inorder(self, root):
        if root:
            self.inorder(root.left)
            self.traverse_path.append(root.val)
            self.inorder(root.right)
    
    def postorder(self, root):
        if root:
            self.postorder(root.left)
            self.postorder(root.right)
            self.traverse_path.append(root.val)
            
if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right = TreeNode(5)
    root.right.left = TreeNode(6)
    
    traver_pre = Traversal()
    traver_pre.preorder(root)
    print traver_pre.traverse_path
    
    traver_in = Traversal()
    traver_in.inorder(root)
    print traver_in.traverse_path
    
    traver_pos = Traversal()
    traver_pos.postorder(root)
    print traver_pos.traverse_path









    



[1, 2, 3, 4, 5, 6]
[3, 2, 4, 1, 6, 5]
[3, 4, 2, 6, 5, 1]

C++

#include <iostream>
#include <vector>

using std::vector;

struct TreeNode
{ // binary tree node
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){}
};

void freeTreeNode(TreeNode* node_ptr)
{ // recursively free memory used by pointers of TreeNode
    if (node_ptr->left != nullptr)
    {
        freeTreeNode(node_ptr->left);
    }
    if (node_ptr->right != nullptr)
    {
        freeTreeNode(node_ptr->right);
    }
    delete node_ptr;
}

class Traversal
{
public:
    Traversal() {}
    void preorder(TreeNode* root)
    {
        if(root != nullptr)
        {
            traverse_path.push_back(root->val);
            preorder(root->left);
            preorder(root->right);
        }
    }

    void inorder(TreeNode* root)
    {
        if(root != nullptr)
        {
            inorder(root->left);
            traverse_path.push_back(root->val);
            inorder(root->right);
        }
    }

    void postorder(TreeNode* root)
    {
        if(root != nullptr)
        {
            postorder(root->left);
            postorder(root->right);
            traverse_path.push_back(root->val);
        }
    }

    std::vector<int> getPath()
    {
        return traverse_path;
    }

private:
    std::vector<int> traverse_path;
};


int main( void)
{
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    // pre-order traversal
    Traversal traver_pre = Traversal();
    traver_pre.preorder(root);
    auto pre_path = traver_pre.getPath();
    for ( std::vector<int>::iterator it = pre_path.begin(); it != pre_path.end(); ++it)
    {
        std::cout << *it << '\t';
    }
    std::cout << '\n';

    // in-order traversal
    Traversal traver_in = Traversal();
    traver_in.inorder(root);
    auto in_path = traver_in.getPath();
    for ( std::vector<int>::iterator it = in_path.begin(); it != in_path.end(); ++it)
    {
        std::cout << *it << '\t';
    }
    std::cout << '\n';

    // post-order traversal
    Traversal traver_post = Traversal();
    traver_post.postorder(root);
    auto post_path = traver_post.getPath();
    for ( std::vector<int>::iterator it = post_path.begin(); it != post_path.end(); ++it)
    {
        std::cout << *it << '\t';
    }
    std::cout << '\n';

    // free memory for TreeNode:
    //delete root;
    freeTreeNode(root);     // recursively delete memory used by TreenNode

    return 0;
}