Binary Tree

-
Definition:


A binary tree   T is a finite set of nodes  with the following properties:
  1. Either the set is empty, tex2html_wrap_inline62586; or
  2. The set consists of a root, r, and exactly two distinct binary trees tex2html_wrap_inline62742 and tex2html_wrap_inline62744, tex2html_wrap_inline62746.
  • The tree tex2html_wrap_inline62742 is called the left subtree  of T, and the tree tex2html_wrap_inline62744 is called the right subtree  of T.
  • They are considered as Ordered subtrees.

  • Level i has  2i  nodes.
In a tree of height h,
  • Leaves are level at h.
  • No of leave are  2h.
  • No of internal nodes 2h    -1.
  • No of internal nodes = no of leaves -1
  • Total no of nodes = 2h+1  -1 =n

In a tree on n nodes 
  • No of leaves is (n+1)/2
  • height =   Log2(n+1)/2

Tree Traversal

  1. PostOrder Traversal
  2. PreOrder  Traversal
  3. InOrder  Traversal

PostOrder Traversal :  In post order tree walks process each node after processing its children.

PreOrder traversal : In preorder tree walk processes each  node before processing its children.

Inorder Traversal :  Besides preorder and postorder , a third possibilities arises when node is visited between visit to  left and right sub tree.



PostOrder : C,B,F ,G E,I,H,D,A

PreOrder : A,B,C,D,E,F,G,H,I

InOrder :B,C,A,F,E,G,D,I,H


Comments

Post a Comment

Popular posts from this blog

JDBC Hive Connection fails : Unable to read HiveServer2 uri from ZooKeeper

-
Image
I have been struggling from couple of days to get my jdbc hive connection working using Zookeeper URI and after putting lot of effort finally I realised problem. In this post I will sharing my experience  and steps I took to rectify problem. Notes : I am having a HDP 2.6 sandbox along with my JDBC program . Use case : Many companies does not provide HiveServer2 url for configuring your JDBC string and its important because if your hiveserver goes down  , your whole job will abort (You will be missing Hive HA capabilities). So How do I dynamically determine second Hive Server URI ? Solution is to use Zookeeper Service Discovery feature. Zookeepers keeps all HiveServer 2 URI into its namespace. When client tries to make a connection to Hive , Zookeeper will look for available hive server and return URL to client program. You can quickly verify HiveServer namespace in zk Path with below command on HDP.  /usr/hdp/current/zookeeper-client/bin/zookeeper-client...
Read more

Access Kubernetes ConfigMap in Spring Boot Application

-
Image
 Hello There, Welcome back to our new post on Kubernetes tutorials. In this example we will see how can we configure and access ConfigMap in Spring boot application. ConfigMaps are helpful where you have multiple environment (Dev,Test Prod etc) and you want to promote your container with different environment configuration. There are three ways Pods can access ConfigMap in containers. For todays Demo , we will use Environment Variable approach. Pre-requisite : MiniKube Cluster   For Demo Purpose I have created Spring Boot application which will expose below end point.  curl localhost:8080/configMap Docker Image : shashivish123/springboot  Below is how Controller class looks like and value is being autowired from application.properties. Remember CONFIG_KEY value will be coming from Kubernetes ConfigMap Environment Configuration. Now Let's Begin , We will start by Creating firs ConfigMap in Kubernetes. Step 1: Create a namespace where we will ...
Read more

Developing Custom Processor in Apache Nifi

-
Image
Apache Nifi was developed to automate the flow of data between different systems. Apache NiFi is based on technology previously called “Niagara Files” that was in development and used at scale within the NSA for the last 8 years and was made available to the Apache Software Foundation through the NSA Technology Transfer Program. Nifi is based on FlowFiles which are heart of it. A FlowFile is a data record, which consists of a pointer to its content (payload) and attributes to support the content, that is associated with one or more provenance events. The attributes are key/value pairs that act as the metadata for the FlowFile, such as the FlowFile filename. The content is the actual data or the payload of the file. Provenance is a record of what’s happened to the FlowFile. Each one of these parts has its own repository (repo) for storage. Each flowfile is processed by FlowFile processor . Processors have access to attributes of a given FlowFile and its content stream. Processo...
Read more